Introduction
In this tutorial we’re going to look at how to calculate the Fibonacci numbers in code. We’ll use two different approaches to this, iterative and recursive, and we’ll examine the pros and cons of both. This tutorial assumes you already know what the Fibonacci numbers are and so I make no attempt to explain the maths behind them.
Also, since this tutorial is more about the algorithm than the programming language used we’re going to implement this using Python because it’s a very easy to read language even if you’ve never used it before. Python is an open-source programming language that is available on just about every platform.
Iteration
First of all, let’s look at the code for an iterative solution:
def __iterative(self, n):
if (n < 2):
return n;
current = 1
previous = 1
for i in range (2, n):
temp = current
current += previous
previous = temp
return current
This function takes n and will calculate the nth number in the Fibonacci sequence, where n is an zero based index. If the first or second numbers are requested (where n is either 0 or 1) then it just returns n as there is nothing to calculate. If any other positive number is requested it starts generating the sequence and accumulating the results.
Let’s take a simple example of where n is 5. Since we’re requesting a number in the sequence that isn’t the first two we need to do a little bit of work. We create two variables called current and previous, where current stores the current number in the sequence we’ve just calculated and previous store the previous one in the range.
Next, we have a loop 2 to n (we start from 2 because 0 and 1 are special cases) and for each iteration of the loop we save current, add previous to current so that current is now the next number in the sequence and then set previous to be what current just was. We complete that process until n equals i. Once the loop ends current will be equal to the nth Fibonacci value.
Let’s see how that works
Step 1: (i = 2, n = 5, i < n = false, current = 1, previous = 1)
current(2) = current(1) + previous(1)
Step 2: (i = 3, n = 5, i < n = false, current = 2, previous = 1)
current(3) = current(2) + previous(1)
Step 3:(i = 4, n = 5, i < n = false, current = 3, previous = 2)
current(5) = current(3) + previous(2)
Step 5:(i = 5, n = 5, i < n = true, current = 5, previous = 3)
end-loop
Result: current = 5
Recursion
Now, let’s look at the code for the recursive version:
def __recursive(self, n):
if (n < 2):
return n;
return self.__recursive(n - 1) + self.__recursive(n - 2)
The first thing to note is that this version is a lot shorter. Let’s look at how it works.
Again, we treat the 0th and 1st case as special in so far as we don’t need to calculate them so the function just returns n. In all other cases where n is positive it returns the result of calculating and adding together the Fibonacci sequence value for n-1 and n-2. So, in the case where n is 5 this function returns the sum of the 4th and 3rd numbers in the Fibonacci sequence.
Eh? Hold on, how does that work? Well, this is a recursive function and, more specifically, this is a recursive function that has 2 paths. In each case one path calculates the result of fib(n-1) and the other calculates the result of fib(n-2). In other words, it’s using a divide and conquer approach, where the function is just creating a new branch for each case of n-1 and n-2 until we hit the special case where n < 2. At that point the recursion for the branch stops and the whole thing unravels.
Let’s look at this using an example of where n is 5.
_recursive(5) _recursive(5) + _recursive(4) _recursive(3) + _recursive(2) + _recursive(2) + 1 _recursive(2) + 1 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1 = 5
Notice how the function calls itself for each branch until n is equal to 1? At that point the recursion of that branch stops and the stack unwinds. Eventually you get to a point where all branches terminate and the result percolates back up the call-stack. In this case it just so happens that when n is 5 the answer is 5 because the 5th number in the Fibonacci sequence is 5.
0 1 1 2 3 [5] 8 …
If n were 8 the result would be 21.
Source
That’s how the iterative and recursive function work and here is the code in full:
#-------------------------------------------------------------------------------
# Name: fibonacci
# Purpose: Examples of iterative and recursive fibonacci calculation
#
# Author: ricky
#
# Created: 01/12/2012
# Copyright: (c) ricky 2012
# Licence:
#-------------------------------------------------------------------------------
class fibonacci:
# Public
def __init__(self, n):
self.reset(n)
def reset(self, n):
self._icnt = 0
self._rcnt = 1
self._ival = self.__iterative(n)
self._rval = self.__recursive(n)
@property
def icnt(self):
return self._icnt
@property
def rcnt(self):
return self._rcnt
@property
def ival(self):
return self._ival
@property
def rval(self):
return self._rval
# Private
def __iterative(self, n):
if (n < 2):
return n;
current = 1
previous = 1
for i in range (2, n):
self._icnt += 1
temp = current
current += previous
previous = temp
return current
def __recursive(self, n):
self._rcnt += 1
if (n < 2):
return n;
return self.__recursive(n - 1) + self.__recursive(n - 2)
def main():
for n in range(0, 21):
fib = fibonacci(n)
print 'ifib({0}): result({1}), evaluations({2})'.format(n, fib.ival, fib.icnt)
print 'rfib({0}): result({1}), evaluations({2})'.format(n, fib.rval, fib.rcnt)
if __name__ == '__main__':
main(
Efficiency
Great so that’s it right? Well, no not quite. You see, although these two functions will calculate the Fibonacci numbers they do it in two very different ways. There are pros and cons to both, can you see what they are?
The main con of the iterative method is that the code is longer (and ugly) and not so easy to follow in terms of mapping what it does to the standard mathematical algorithm is normally expressed 
Programming algorithms and mathematical algorithms are not the same thing and just because you can express an algorithm in code so it looks like its mathematical counter-part doesn’t mean that is the best way to code that algorithm. Mathematical algorithms don’t need to take into account efficiency (either time or space). Unfortunately, programming algorithms most certainly do. We’d like our calculation to complete at some point, preferably as quick as possible.
So, what’s wrong with the recursive solution I hear you cry? Well, try running the full code, above, and read the output on the screen. More specifically, look at the number of “evaluations” each version needs to perform to get the result. In the example code we calculate up to the 21st number in the sequence. To calculate the 21st number the iterative version requires 19 evaluations. The time complexity is linear 
Let’s visualise this to see exactly what happens when you call the recursive version for the 8th number in the series:
As you can see, the result of the recursive version is a tree of calls that only terminate once a branches leaf is 1. The Fibonacci number ends up being the number of leafs of each branch (in this case there are 21 since that is the 8th Fibonacci number).
Time complexity isn’t the only case where the recursive approach is a bad idea. Consider that each recursion requires space on the stack. This means that space complexity is also exponential, compared to the iterative version that is constant as it just uses the same 3 variables for each iteration.
Summary
So, to summarise, whilst it is possible to calculate the Fibonacci sequence using recursion this is really not the best example of using recursion and if you really do need to calculate using a simple algorithm it is better to go with an iterative approach.
evilrix 