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.
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.