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
[ Parent
| on HN ]
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.