Recursion vs. Iteration (Fibonacci sequence)

For terseness, Let F(x) be the recursive Fibonacci

F(10) = F(9)                      + F(8)
F(10) = F(8)        + F(7)        + F(7) + F(6)
F(10) = F(7) + F(6) + F(6) + F(5) + 4 more calls.
....

So your are calling F(8) twice, F(7) 3 times, F(6) 5 times, F(5) 7 times.. and so on

So with larger inputs, the tree gets bigger and bigger.

This article does a comparison between recursion and iteration and covers their application on generating fibonacci numbers.

As noted in the article,

The reason for the poor performance is heavy push-pop of the registers in the ill level of each recursive call.

which basically says there is more overhead in the recursive method.

Also, take a look at Memoization

When doing the recursive implementation of Fibonacci algorithm, you are adding redundant calls by recomputing the same values over and over again.

fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)

Notice, that fib(2) will be redundantly calculated both for fib(4) and for fib(3). However this can be overcome by a technique called Memoization, that improves the efficiency of recursive Fibonacci by storing the values, you have calculated once. Further calls of fib(x) for known values may be replaced by a simple lookup, eliminating the need for further recursive calls.

This is the main difference between the iterative and recursive approaches, if you are interested, there are also other, more efficient algorithms of calculating Fibonacci numbers.

Why is Recursion slower?

When you call your function again itself (as recursion) the compiler allocates new Activation Record (Just think as an ordinary Stack) for that new function. That stack is used to keep your states, variables, and addresses. Compiler creates a stack for each function and this creation process continues until the base case is reached. So, when the data size becomes larger, compiler needs large stack segment to calculate the whole process. Calculating and managing those Records is also counted during this process.

Also, in recursion, the stack segment is being raised during run-time. Compiler does not know how much memory will be occupied during compile time.

That is why if you don't handle your Base case properly, you will get StackOverflow exception :).