4 ms·
> 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
by DonaldPShimoda 8y ago
> 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.
- gameswithgo 8y agosome compilers can rearrange it to be tail recursive automatically
- SeanLuke 8y agoWhich compilers can rearrange fib, with two recursive calls, into being tail recursive?
- FeepingCreature 8y agoIf it knows it's a pure function, it's possible. It'd have to be a very specific optimization pass though.
- jcranmer 8y agoAny LLVM-based compiler. GCC.
- Jtsummers 8y agoPretend 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.
- FeepingCreature 8y agoFun challenge. https://paste.pound-python.org/show/m403qNkpS5I8dnYjJGJq/ https://paste.pound-python.org/show/m403qNkpS5I8dnYjJGJq/ I wanna see the compiler that gets that.
- DonaldPShimoda 8y agoBut that doesn't make it "poster boy" material, in my opinion.
- rothron 8y agoI 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.