Fibonacci series using recursion and dynamic programming

Fibonacci series is a series of Fibonacci numbers. A Fibonacci number is denoted as the sum of its two preceding numbers in the series. These numbers are starting from 0 and 1. Let’s see the mathematical formula for the Fibonacci number.

// Let's take N-th fibonacci number denoted as F(n)
F(n) = 0                 // Where n is 0
     = 1                 // Where n is 1
     = F(n-1) + F(n-2)   // Where n is greater than 1.

There is an exponential number of real-world applications on the Fibonacci numbers.

This is fibonacci tiling image. Source: Wikipedia.

As per the mathematical formula, this is a recursive function which can be solved using recursion. Every recursion can also be solved using Dynamic programming.

  1. Recursion Approach
  2. Dynamic Programming approach.

Fibonacci series using recursion

Recursion solution is based on the mathematical formula. Let’s see the code for this problem.

// Find n-th fibonacci number (Recursively).
int fibonacciRecur(int n)
{
    if (n == 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    else
    {
        return fibonacciRecur(n - 1) + fibonacciRecur(n - 2);
    }
}
// To print first n-fibonacci numbers.
void printFibonacciRec(int n)
{
    int i;
    for (i = 0; i < n; i++)
    {
        cout << fibonacciRecur(i) << " ";
    }
    cout << endl;
}

The complexity of this problem is exponential which is O(2^n). And recursion solution also has too many overlaps which computes the same problem multiple times as showing in the below picture.

Recursion tree of a Fibonacci series, which has a couple of overlaps. As this tree grows the overlaps increase exponentially.

To overcome this overlaps problem we use Dynamic Programming (DP).

Dynamic Programming approach

In Dynamic Programming we memorize each result in an array and use the same whenever required (don’t need to calculate again). Let’s see the code for this approach.

// Find n-th fibonacci number (dynamic programming).
int fibonaccidp(int arr[], int n)
{
    if (n == 0)
    {
        arr[n] = 0;
    }
    else if (n == 1)
    {
        arr[n] = 1;
    }
    else
    {
        arr[n] = arr[n - 1] + arr[n - 2];
    }
    return arr[n];
}
// To print first n-fibonacci number using DP.
void printFibonacciDP(int n)
{
    int arr[n];
    int i;
    for (i = 0; i < n; i++)
    {
        cout << fibonaccidp(arr, i) << " ";
    }
    cout << endl;
}

This has complexity of O(n) to find n-th fibonacci, and uses an O(n) space.

This is all about the Fibonacci series and its implementation using recursion and Dynamic programming. If you know any better approach to solve this, please let our readers know by commenting below. Happy learning!.

Advertisements