# Fibonacci Numbers

July 30, 2019 4 minutes

Fibonacci Numbers, named after the great Italian mathematician of the same name, are so popular that theres even a mathematical journal (The FIbonacci Quarterly) dedicated to their theory and applications.

From golden ratio (also known as phi), to their appearance in various natural settings like branches of a tree, seed patterns of a sunflower, veins of leaves and many more, fibonacci numbers can be found almost everywhere.

### Recurrence Relation

Mathematically, the $n^{th}$ fibonacci number can be represented as the sum of two previous fibonacci numbers: $F_{n}=F_{n-1}+F_{n-2}$ with a set of given initial values:

• $F(0)=0$
• $F(1)=1$
• $F(2)=1$
• $F(3)=2$
• $F(4)=3$ and so-on

So the first $10$ terms of the sequence are: $0,1,1,2,3,5,8,13,21,34$

### Golden Ratio

Two consecutive entries of a fibonacci series are found to be closely approaching to the Golden Ratio. The ratio, also known as phi ($\varphi$), is an irrational number approximately equal to 1.6180339887..

The Golden Ratio is said to be found in many natural, geometrical, art and other settings. It is a general preception that the shapes or structures following this ratio are relatively more pleasing to the eye as compared to others.

### Pseudo Code

1. Initialize
• n = the ith term of fib series that we need to find
2. Check if n == 1 or 0; this condition acts as base case for the recursive algorithm
• If yes, return 0 without calling the method recursively
3. Call the method again for:
• n = n-1
• and n = n-2
4. Add the results of above two calls and return the same.

### Java Implementation

The following program can be used to recursively find the $n^{th}$ term of a fibonacci series:

// if n == 1 or 0; return 0
// for every other value of n
// call the method recursively for n-1 and n-2
// and return the sum of these two calls
public int fibonacci(int n) {
return (n == 1) ? 1 : (n < 1) ? 0 : fibonacci(n - 1) + fibonacci(n - 2);
}


As clear from the above recursion tree, we can see that two different branches of the tree can lead to some repititive calculations. For example:

1. F(3) is evaluated twice.
2. F(2) is evaluated thrice.
3. F(1) is evaluated 5 times and so-on.

For a considerably large number, this repeated calculatioon can actually lead to program crash. So how do we avoid this?

It turns out that there are a few options that we can use to avoid these repetitive calculations. The first one is to use an iterative approach to calculate the $n^{th}$ fibonacci number. As it does not requires any additional stacks to hold the temporary state, its more space optimized version as compared to the above mentioned:

// calculate nth fibonacci number using
// iterative approach instead of recursive approach
public int fibonacciCalculator(int n) {
int first = 1, second = 1, result = 0;
while (n > 2) { // as first two terms are fixed
result = first + second;
first = second;
second = result;
n--;
}
return result;
}


Another approach is to use dynamic programming to calculate $n^{th}$ fibonacci term. As clear from the recursion tree, we can see that the calculation actually follows the two pre-requisite conditions for the applicability of dynamic programming:

1. Overlapping Subproblems: The solution of sub-problems can be used over and again to calculate the solution of the overall problem.
2. Optimal Substructure: The overall solution can be build by using the combined solution of the subproblems.

The following program shows how to use dynamic programming to get $n^{th}$ fibonacci number:

// calculate nth fibonacci number using dynamic programming
public int fibonacciCalculator(int n) {
int[] fib = new int[n + 1];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}