The Fibonacci sequence is defined as follows:
This definition is recursive, since the definition of "fib" depends on itself. This recursive definition indicates the following simple recursive implementation:
This function is recursive because it calls itself.
This naive implementation has several problems though:
You can define the Fibonacci sequence in terms of a recurrence relation:
Notice that fib(n) depends on two values: the previous two numbers in the sequence. What if we stored these last two numbers when calculating the next number? Let's call the previous two numbers a and b. At each iteration i, the next number c is just a + b:
Once we compute the next number, we must update our old a and b:
This indicates the following iterative implementation:
Notice that we have removed the recursion from this implementation. The new fib does not depend on itself. Instead, the function is implemented as a for-loop which computes the next number in the sequence based on the previous two numbers.
The implementation is very efficient, because we only store the values we need for the next iteration (a, b, and c).