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