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);
}

FibonacciNumbers

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];
}

Some Common Questions

  1. Brick Wall Patterns
  2. Leonardo’s Lane

Additional Readings

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

comments powered by Disqus