[dmlorenzetti]

The recursive approach isn't necessarily worse, provided the compiler can do a so-called "tail call optimization" (in the original posting, note the line that says of the compiler optimization level, "We need -O2 so gcc will recognize the tail-call.").

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.

[aeon10]

Yes, I understand that recursion is much more appealing and leads to much cleaner and elegant code than iterative solutions. and thank you for the introduction to the community I suppose.

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.

[aeon10]

Just a note, In the iterative solution, by changing the i (loop variable) from an int to an long int the times by both iterative and recursive are almost equal. Here are the new results

[Recursive - 7921 ms], [Iteratiive - 8078 ms]

So the difference is negligible.

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