Fibonacci Series Using Recursion

In this lesson, we'll look at the classic method to find the nth Fibonacci number and its time complexity using recurrence relations.

We'll cover the following

Classic recursive implementation of the Fibonacci series

Before we dive into what dynamic programming is, let’s have a look at a classic programming problem, the Fibonacci Series. You have probably already seen it, but let’s start with a quick refresher. The Fibonacci series is a series of numbers in which each number is the sum of the preceding two numbers. The first two numbers are 0 and 1. So, it looks like:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Here is a Java function that returns nth the Fibonacci number.

Here is the Fibonacci Golden Spiral. The width of each square represents a Fibonacci number.
class Fibonacci {
 //Finds nth fibonacci number
 public static int fib(int i) {
  if (i <= 1)
   return i;
  return fib(i - 1) + fib(i - 2);
 }
 //driver code to test the function
 public static void main(String args[]) {
  System.out.println(fib(6));
 }
};

Time complexity with recurrence relations

To calculate the time complexity of the code, we can solve a recurrence relation:

{T(0)=0,T(1)=1,T(n)=T(n−1)+T(n−2)+4\begin{cases} T(0) = 0, \\ T(1) = 1, \\ T(n) = T(n-1)+T(n-2)+4 \end{cases}

T(n)T(n) represents the fib function. T(n−1)T(n-1) and T(n−2)T(n-2) represent the recursive calls to fib(n-1) fib(n-2), whereas the ‘4’ represents the basic operations in the code. Namely, the comparison on line 4 and the two subtractions and one addition on line 6. Lastly, T(1)=1T(1) = 1 and T(0)=1T(0) = 1 represent the base-cases.

To solve this recurrence, we can simplify it by approximating that T(n−1)≈T(n−2)T(n-1) \approx T(n-2). The time that is taken to calculate T(n−1)T(n-1) is greater than the time taken to calculate T(n−2)T(n-2), so this approximation gives us an upper bound on the total time complexity:

eq 1: T(n)=2T(n−1)+4T(n) = 2T(n-1)+4

Replacing nn by n−1n-1 on both sides:

eq 2: T(n−1)=2T(n−2)+cT(n-1) = 2T(n-2)+c where c=4c = 4

So, we can replace T(n−1)T(n−1) in eq 1 with the value of it in eq 2 to get:

T(n)=2(2T(n−2)+c)+cT(n) = 2(2T(n-2)+c)+c

= 4T(n−2)+3c4T(n-2)+3c

= 4(2T(n−3)+c)+3c4(2T(n-3)+c)+3c

= 8T(n−3)+7c8T(n-3)+7c

⋯\cdots

You must have noticed a pattern here, which means that this equation can be written in generic terms.

generic: T(n)=2kT(n−k)+(2k−1)c T(n) = 2^kT(n-k)+(2^k-1)c \space

where kk is the number of times that the equation was substituted into. Have a look at the following for a clearer picture:

T(n)=2T(n−1)+c            k=1T(n) = 2T(n-1)+c \;\;\;\;\;\; \color{red} k \color{red}= \color{red}1

T(n)=4T(n−2)+3c        k=2T(n) = 4T(n-2)+3c \;\;\;\; \color{red} k \color{red}= \color{red}2

T(n)=8T(n−3)+7c        k=3T(n) = 8T(n-3)+7c \;\;\;\; \color{red} k \color{red}= \color{red}3

⋯\cdots

Let’s consider what value of kk brings the argument of T(n−k)T(n-k) to the base case of 1. If n−k=1n - k = 1, then k=n−1k = n - 1. Next, we substitute k = n - 1 in the expression for T(n)T(n). We can now put the generic equation in terms of T(1)T(1), the value of which we know is 11:

T(n)=2n−1+(2n−1−1)cT(n) = 2^{n-1}+(2^{n-1}-1)c

=2n−1+c2n−1−c= 2^{n-1}+ c2^{n-1}-c

=2n−1(1+c)−c = 2^{n-1}(1+ c)-c \space

Hence,

T(n)=2n−1(1+c)−cT(n) = 2^{n-1}(1+ c)-c

This means that the fib(n) function is in O(2n)O(2^n), i.e., exponential time, which isn’t very efficient. What is causing this inefficiency and how can we improve this? Let’s take a look at that now.

Redundant calculations

One factor is that some terms of fib(n) are calculated several times. Look at the following slides to see which ones are repeated in the case of fib(6):