### Fibonacci Numbers in C\C++

December 11, 2015 | Article | No Comments

In mathematics, Fibonacci numbers or Fibonacci sequence are the numbers in the following integer sequence:

or:

In mathematical terms, the Fibonacci sequence Fn is defined by the recurrence relation

with seed values

Our task is to write a function that returns Fn. Following are different methods to get the nth Fibonacci number

### Method 1: Simple and Naive Recursion

A simple recursion that implementing the Fibonacci definition above.

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

Time complexity: T(n) = T(n-1) + T(n-2) which is exponential.

This implementation does a lot of repeated work (see below).

fib(5) / \ fib(4) fib(3) / \ / \ fib(3) fib(2) fib(2) fib(1) / \ / \ / \ fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) / \ fib(1) fib(0)

Extra space: O(n) if we consider function call stack size. Otherwise O(1)

### Method 2: Dynamic Programming – Top Down Approach

We can void the repeated work by storing the numbers calculated so far.

/* the real function to compute the fibonacci numbers */ int _fib(int * st, int n) { /* if the value has not stored yet, computed it */ if (st[n] == -1) { st[n] = _fib(st, n-1) + _fib(st, n-2); } return st[n]; } /* a wrapper function */ int fib(int n) { /* array to store the fibonacci numbers */ int st[n+1]; int res; int i; st[0] = 0; st[1] = 1; for (i=2; i<=n; i++) { st[i] = -1; } _fib(st, n); return st[n]; }

Time complexity: O(n)

Extra space: O(n)

### Method 3: Dynamic Programming – Bottom Up Approach

Another approach which also store the calculated number so far.

int fib(int n) { int st[n+1]; int i; st[0] = 0; st[1] = 1; for (i=2; i<= n; i++) { st[i] = st[i-1] + st[i-2]; } return st[n]; }

Time complexity: O(n)

Extra space: O(n)

### Method 4: Dynamic Programming – Space Optimized Method 3

We can optimize the space used in method 3 by storing the previous two numbers only because that are all we need to get the next Fibonacci numbers.

int fib(int n) { int a = 0, b = 1, c; int i; for (i=2; i<=n; i++) { c = a + b; a = b; b = c; } return b; }

Time complexity: O(n)

Extra space: O(1)

### Method 5: Using Matrix

This method relies on 2-dimensional system of linear difference equations for Fibonacci sequence. If we n times multiply the matrix M = {{1,1}, {1,0}} to itself (in other word calculate power(M, n)) then we get the (n+1)th Fibonacci number as the element at row and column (0,0) in the resultant matrix.

Here is how we do that:

/* Helper functions */ void multiply(int F[2][2], int M[2][2]); void power1(int F[2][2], int n); int fib(int n) { /* We don't need to compute the matrix for these values */ if (n<2) return n; int F[2][2] = {{1,1}, {1,0}}; power(F, n-1); return F[0][0]; } /* multiply 2 matrices F and M of size 2*2 and puts the result back to F */ void multiply(int F[2][2], int M[2][2]) { int w = F[0][0] * M[0][0] + F[0][1] * M[1][0]; int x = F[0][0] * M[0][1] + F[0][1] * M[1][1]; int y = F[1][0] * M[0][0] + F[1][1] * M[1][0]; int z = F[1][0] * M[0][0] + F[1][1] * M[1][1]; F[0][0] = w; F[0][1] = x; F[1][0] = y; F[1][1] = z; } /* designed for fib only */ void power(int F[2][2], int n) { int i; int M[2][2] = {{1,1}, {1,0}}; for (i=2; i<=n; i++) { multiply(F, M); } }

Time complexity: O(n)

Extra space: O(1)

### Method 6: Using Matrix – Optimized Method 5

The method 5 can be optimized to work in O(log n) time complexity. By implementing the Divide and Conquer to power and multiplication, we can do better.

/* Helper functions */ void multiply(int F[2][2], int M[2][2]); void power(int F[2][2], int n); int fib4(int n) { if (n<2) return n; int F[2][2] = {{1,1}, {1,0}}; power(F, n-1); return F[0][0]; } /* multiply 2 matrices F and M of size 2*2 and puts the result back to F */ void multiply(int F[2][2], int M[2][2]) { int w = F[0][0] * M[0][0] + F[0][1] * M[1][0]; int x = F[0][0] * M[0][1] + F[0][1] * M[1][1]; int y = F[1][0] * M[0][0] + F[1][1] * M[1][0]; int z = F[1][0] * M[0][0] + F[1][1] * M[1][1]; F[0][0] = w; F[0][1] = x; F[1][0] = y; F[1][1] = z; } /* designed for fib only, optimized it using Divide and Conquer */ void power(int F[2][2], int n) { if (n==0 || n==1) return; int M[2][2] = {{1,1}, {1,0}}; power(F, n/2); multiply(F, F); if (n%2) { multiply(F, M); } }

Time complexity: O(log n)

Extra space: O(log n) if we consider the function call stack size, otherwise O(1)