News for hackers. Stuff that matters.
Re:Recursive fibonacci benchmark using top languages on GitHub by DonaldPShimoda on Friday September 28, 2018 @10:33AM (#18093675)
> Fib is the poster boy for tail recursion

But recursive Fibonacci isn't tail recursive. The final function call is to `+` (addition), which means that the two recursive calls must each be put on the stack and later returned so the sum can be computed. Tail recursion requires that there is no final operation other than exactly a single recursive call.

Re:Recursive fibonacci benchmark using top languages on GitHub by gameswithgo on Friday September 28, 2018 @10:59AM (#18093890)
some compilers can rearrange it to be tail recursive automatically
Re:Recursive fibonacci benchmark using top languages on GitHub by Jtsummers on Friday September 28, 2018 @12:25PM (#18094641)
Pretend you're a compiler, what changes would you make to this to make it tail recursive:

  fib(0) -> 1;
  fib(1) -> 1;
  fib(N) -> fib(N-1) + fib(N-2).
Rules: Making a second function (fib_help) is permitted. Shouldn't use any more memory than this one uses.
Re:Recursive fibonacci benchmark using top languages on GitHub by FeepingCreature on Friday September 28, 2018 @02:15PM (#18095639)
Fun challenge.

https://paste.pound-python.org/show/m403qNkpS5I8dnYjJGJq/

I wanna see the compiler that gets that.

Re:Recursive fibonacci benchmark using top languages on GitHub by SeanLuke on Friday September 28, 2018 @11:56AM (#18094421)
Which compilers can rearrange fib, with two recursive calls, into being tail recursive?
Re:Recursive fibonacci benchmark using top languages on GitHub by FeepingCreature on Friday September 28, 2018 @02:18PM (#18095673)
If it knows it's a pure function, it's possible. It'd have to be a very specific optimization pass though.
Re:Recursive fibonacci benchmark using top languages on GitHub by jcranmer on Friday September 28, 2018 @04:49PM (#18096955)
Any LLVM-based compiler. GCC.
Re:Recursive fibonacci benchmark using top languages on GitHub by DonaldPShimoda on Friday September 28, 2018 @06:27PM (#18097580)
But that doesn't make it "poster boy" material, in my opinion.
Re:Recursive fibonacci benchmark using top languages on GitHub by rothron on Sunday September 30, 2018 @07:29AM (#18105709)
I called it that because I've seen fib be the go-to example of so many introductions to functional programming.

But I suppose it's more accurate to describe it as the poster boy example for changing an implementation to make it tail recurse.