Fibonacci is a well known number sequence that models the growth of a rabbit population amongst other things found in nature.

The Fibonacci Numbers Sequence

Below is the Fibonacci numbers computed up to the 11th term.

The formula for Fibonacci

Computing for Fibonacci is simple. The formula is below.

Fibonacci (n) = Fibonacci(n-1) + Fibonacci(n-2);

To computer for Fibonacci of 7, simply add the values of Fibonacci of 6 and Fibonacci of 5. In other words, the sum of the previous two values.

Fibonacci(7) = Fibonacci(6) + Fibonacci(5);
Fibonacci(7) = 8 + 5;
Fibonacci(7) = 13;

Iterative version of Fibonacci

This is an iterative version of Fibonacci.

int fib(int n) {
    if ( n == 0 || n == 1 ) 
        return n;
 
    int fib1 = 0; 
    int fib2 = 1;
    int fib = 0;
 
    for ( int i = 2; i < n; i++ ) 
    {
        fib = fib1 + fib2;
        fib1 = fib2;
        fib2 = fib;
    }
 
    return fib;
}

Recursive version of Fibononacci

The recursive version of Fibonacci in C++ is below. This recursive function computes the sum of the previous two fibonacci numbers recursively.

int fib(int n)
{
     if ( n == 0 ) return 0;
     if ( n == 1 ) return 1;
 
     return fib(n-1) + fib(n-2);
}

An image of how this recursive solution works is below. Each bubble is a function call.

Dynamic Programming version of Fibonacci

The dynamic programming version of Fibonacci in C++ is below. This snippet of code computes the fibonacci by traversing a vector.

 
vector <int> fib;
fib.push_back(0);
fib.push_back(1);
 
int n; //N is the number of fibonacci numbers we are going to compute. 
 
for ( int i = 2; i < n; i++ ) 
{
      fib.push_back( fib[i-1] + fib[i-2] );
}

Finishing remarks

So, which one do you think is the fastest version?