[algorias]

Tail call optimization does nothing to mitigate the fact that it takes an exponential number of recursive calls to calculate fibonacci. Just draw the call tree of f(5) by hand to see what happens.

>My impression is that most people here understand that a simple for-loop will get the job done, but they don't see for-loops as very interesting

Well, let's make them a bit more interesting then... The simple for loop is actually an example of dynamic programming, i.e. building a table of values from the bottom up in order to avoid repeated calculations. In this case the table only needs to have size 2, as an entry won't be read ever again after the first 2 uses.

[dwyer]

1. The worst case for fibonacci is not exponential, it's actually O(fib(n)).

2. The recursive function `fib_helper` in TFA is actually iterative in an TCO environment. Read it closely. There's only on recursive call at the end, not two. `back_one` and `back_two` mean fib(x-1) and fib(x-2) respectively, the same way you would solve it with a loop. With the right `CFLAGS` it should produce more or less the same bytecode.