Hacker News Reader

Comment by gameswithgo | Hacker News Reader

some compilers can rearrange it to be tail recursive automatically

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.

Fun challenge.

I wanna see the compiler that gets that.

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

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

Any LLVM-based compiler. GCC.

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

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.