Embed from Getty Images

Fibonacci Series:

Fibonacci series is a series of numbers which are built up based on previous numbers.

Example:

f(1) – The first number in sequence is 0.

f(2) – The second number in sequence is 1.

f(3) – Third number is Second number + First number = 0 + 1 = 1.

f(4) – Fourth Number is Third number + Second number = 1 + 1 = 2.

f(5) – Fifth Number is Fourth number + Third number = 2 + 1 = 3.

First 10 numbers in series are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

In this article, I will generate the Fibonacci series using recursion and iteration.

Recurrence relation for Fibonacci Series is:

The recurrence relation means:

• If n = 0, then return 0
• If n = 1, then return 1
• If n = 0, then return F_n-1 + F_n-2

Generating Fibonacci series using Recursion

Code for recursion is:

public static int fiboRec(int limit){
    if (limit == 0) return 0;

    if (limit == 1) return 1;

    return fiboRec(limit - 1) + fiboRec(limit - 2);

}

Recursion Tree.

Picture taken from https://www.cs.cmu.edu/~adamchik/15-121/lectures/Recursions/recursions.html

Above is the recursion tree. In tree there are several values which are computed repeatedly. For example, let’s take F(3). F(3) is computed by F(5) and as well as by F(4). For small values, this solution can work, but for big value n this solution isn’t optimal. Let us run some benchmarks for a recursion solution. Remember, these benchmarks may vary based on several unique attributes. I am running these benchmarks on a MacBook pro 16GB RAM.

i = 0: result is 0: time taken is 0 milliseconds

i = 5: result is 5: time taken is 0 milliseconds

i = 10: result is 55: time taken is 0 milliseconds

i = 15: result is 610: time taken is 0 milliseconds

i = 20: result is 6765: time taken is 0 milliseconds

i = 25: result is 75025: time taken is 1 milliseconds

i = 30: result is 832040: time taken is 5 milliseconds

i = 35: result is 9227465: time taken is 53 milliseconds

i = 40: result is 102334155: time taken is 639 milliseconds

i = 45: result is 1134903170: time taken is 6795 milliseconds

So we conclude that time takes to execute the recursive solution it high. The reason is that the recursion tree becomes too much dense and several values are computed again and again.

Generating Fibonacci series using Iteration

public static int fiboIterative(int limit) {
    int count = 0;
    int a = 0, b = 1;
    for (int i = 0; i < limit - 1; i++) {
        count = a + b;
        a = b;
        b = count;
    }
    return count;
}

For the iterative method, we just add the previous 2 numbers and built the next two numbers by copying them into variables.

Let us run some benchmarks for an iterative solution.

i = 0: result is 0: time taken is 0 milliseconds

i = 5: result is 5: time taken is 0 milliseconds

i = 10: result is 55: time taken is 0 milliseconds

i = 15: result is 610: time taken is 0 milliseconds

i = 20: result is 6765: time taken is 0 milliseconds

i = 25: result is 75025: time taken is 0 milliseconds

i = 30: result is 832040: time taken is 0 milliseconds

i = 35: result is 9227465: time taken is 0 milliseconds

i = 40: result is 102334155: time taken is 0 milliseconds

i = 45: result is 1134903170: time taken is 0 milliseconds

Iteration is a better way to generate Fibonacci series rather than recursive, as it takes significantly less time than its recursive counter part.