# Fibonacci Numbers

**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

- Initialize
- n = the ith term of fib series that we need to find

- 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

- Call the method again for:
**n = n-1**- and
**n = n-2**

- 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:

**F(3)**is evaluated twice.**F(2)**is evaluated thrice.**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:

**Overlapping Subproblems**: The solution of sub-problems can be used over and again to calculate the solution of the overall problem.**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];
}
```

### Some Common Questions

### Additional Readings

If you are interested, you can refer to this excellent article for more information and properties of fibonacci numbers.