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

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.

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

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.

It can be a gateway for learning interesting things about the mechanics of a language, its compilation, and in turn how to make similar cases in other languages faster/cleaner/more-secure. e.g. why is nim so fast in this case? Is it tail call optimisation, not doing overflow checks, static inlining, or something else? Nim compiles to c to it is especially odd.

Why would languages without tail recursion optimisation perform worse when all languages use the naive implementation? It's not tail recursive, so it shouldn't make a difference, right?

You're right that tail recursion doesn't help - the final operation is the addition, not a recursive call.

Just to underline the futility of this, if you are clever you can let the compiler do it.

https://everything2.com/title/C%252B%252B%253A+computing+Fib...

The benchmark includes a C++ constexpr version, at https://github.com/drujensen/fib/blob/master/fib-constexpr.c... , with timing numbers under the section "Optimized code that breaks the benchmark" and the comment "all benchmarks will have some caveat."

Somewhat off topic, but I love the fact that the first post regarding compile-time Fibonacci in C++ was submitted in 2000, another user expanded on the original in 2008, and now it's being usefully referenced in 2018.

I stumbled across Everything2 recently, but in many ways it strikes me as a tiny bit of the golden age of the internet, unexpectedly preserved.