[DonaldPShimoda]

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

some compilers can rearrange it to be tail recursive automatically

[Jtsummers]

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.

[FeepingCreature]

Fun challenge.

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

I wanna see the compiler that gets that.

[SeanLuke]

Which compilers can rearrange fib, with two recursive calls, into being tail recursive?

[FeepingCreature]

If it knows it's a pure function, it's possible. It'd have to be a very specific optimization pass though.

[jcranmer]

Any LLVM-based compiler. GCC.

[DonaldPShimoda]

But that doesn't make it "poster boy" material, in my opinion.

[rothron]

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.