Problem

The Fibonacci Numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

Sequence is defined as, $$ F_{0} = 0 $$ and $$ F_{1} = 1 $$ and $$ F_{n} = F_{n-1} + F_{n-2} $$

Given n, calculate F(n).

Examples

Example 1:

Input : n = 2
Output : 1

Example 2:

Input : n = 9
Output : 34

Method 1 - Use Recursion

A simple method that is a direct recursive implementation mathematical recurrence relation given above.

public int fib(int n) {
	if (n <= 1) {
		return n;
	}

	return fib(n - 1) + fib(n - 2);
}

Time Complexity

  • Time Complexity: T(n) = T(n-1) + T(n-2) = O(2^n) which is exponential.
  • Space complexity: O(1) (assuming recursive stack is okay)

We can observe that this implementation does a lot of repeated work (see the following recursion tree below, where F(3) and F(2) is calculated twice). So this is a bad implementation for nth Fibonacci number.

Recursion tree for execution of fib(5):

Method 2 - Top Down DP

As we saw above, this problem shows the overlapping subproblems pattern, so let’s make use of memoization here. We can use an array to store the already solved subproblems (see the changes in the highlighted lines).

Code

Java
public int fib(int n) {
	int memo[] = new int[n + 1];
	return fibRecursive(n, memo);
}


public int fibRecursive(int n, int[] memo) {
	if (n < 2)
		return n;

	// if we have already solved this subproblem, simply return the result from the cache
	if (memo[n] != 0)
		return memoize[n];

	memo[n] = fibRecursive(memo, n - 1) + fibRecursive(memo, n - 2);
	return memo[n];
}
C++

std::function<int(int)> f = [&] (int x) { return (x < 2) ? x : f(x-1) +
f(x-2); };

Optimized Version:

std::vector<int> cache = {0, 1};
    
     std::function<int(int)> f = [&] (int x)
     {
         if (cache.size() > x) return cache[x];
        
         cache.push_back(f(x-1) + f(x-2));
        
         return cache.back();

    };

Method 3 - Bottom Up DP

Let’s apply Tabulation to our example of Fibonacci numbers. Since we know that every Fibonacci number is the sum of the two preceding numbers, we can use this fact to populate our table.

Code

Java
public int fib(int n) {
	if (n == 0) return 0;
	int dp[] = new int[n + 1];

	//base cases
	dp[0] = 0;
	dp[1] = 1;

	for (int i = 2; i <= n; i++)
		dp[i] = dp[i - 1] + dp[i - 2];

	return dp[n];
}

Time Complexity: O(n) Extra Space: O(n)

Method 4 - Space Optimized DP

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

Code

Java
public int fib(int n) {
	if (n == 0) {
		return 0;
	} else if (n == 1) {
		return 1;
	}

	int a = 0, b = 1;

	for (int i = 2; i <= n; i++) {
		int c = a + b;
		a = b;
		b = c;
	}

	return b;
}

Time Complexity: O(n) Extra Space: O(1)

Method 5 - Using power of the matrix

Lets assume the notation:

  • Non-negative integers:

$$ N_0 = {0, 1, 2, 3, \dots } $$

  • Positive integers

$$ N_1 = {1, 2, 3, \dots } $$

#TODO: complete

Method 6 - Using Formula

Can there be formula for Fibonacci numbers in terms of n? Answer is yes.

The formula is called Binet’s formula. It uses something called golden ratio.

Golden Ratio (φ)

  • An irrational number approximately equal to 1.6180339887…
  • Can be expressed mathematically as: φ = (1 + √5) / 2

Binet’s Formula

$$ \phi = \frac{\phi ^ n - \phi ^ {-n}}{\sqrt{5}} $$

Limitations

However, this formula has limitations:

  • It involves powers of φ, which is an irrational number. Calculating exact values with an irrational number can be complex, especially for larger n.
  • The square root of 5 (√5) is another irrational number, adding further complexity.

Therefore, Binet’s formula is not typically used for practical calculations of Fibonacci numbers due to its reliance on irrational numbers.