If im not mistaken the iterative solution of using a simple for loop would definitely be insanely faster than a recursive algorithm which is exponential.. What am i missing here?
Tail-call optimization says that if a function directly returns the result of calling another function, then you don't need to add to the call stack in order to effect the function call-- you just modify the current stack frame as needed. For a recursive function, apparently a good compiler can essentially transform this into code very similar to what you'd get with an explicit loop.
None of this means that a simple for-loop wouldn't be appropriate, or even faster. Personally I use for-loops a lot, and, like you, I would naturally incline to writing this using a loop rather than recursion.
I see yours is a new account, so maybe this is just a cultural thing that I've got used to. To generalize grossly, recursion is more fashionable on HN than iteration. Every once in a while you'll see a post here that touches on iteration-- like maybe somebody will mention the tradeoffs between counting down and counting up a loop variable. But guaranteed at least once a week you'll see something on recursion and functional programming.
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, and don't figure it adds anything to the discussion to bring it up.
Meanwhile, there are people here who will actively advocate against using for-loops. There's a whole theory of functional languages that says that if your program doesn't directly modify variables, then it's easier to reason about. A for-loop modifies the trip variable, so it's not a functional construct.
Anyway I forked the original code, added an iterative version based on the comment by (Nick Craig Wood) (https://github.com/AeonAxan/benchmarking_fibonacci)
Here are the benchmarks [recursive fib: 7,765 ms] | [iterative fib: 8,047 ms] | [analytic opt fib: 54,875] | [analytic fib: 103,937 ms] |
And it appears that the recursive version is faster than the naive iterative version by a few hundred milliseconds.
[Recursive - 7921 ms], [Iteratiive - 8078 ms]
So the difference is negligible.
>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.
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.
In general, a recursive solution need never have a bigger big-O than an iterative solution. You just need to define a helper function that has a many input parameters as your for-loop had variables that it updates.