# 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.

## 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.

class Fibonacci {//Finds nth fibonacci numberpublic static int fib(int i) {if (i <= 1)return i;return fib(i - 1) + fib(i - 2);}//driver code to test the functionpublic 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:

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

$T(n)$ represents the `fib`

function. $T(n-1)$ and $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) = 1$ and $T(0) = 1$ represent the base-cases.

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

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

Replacing $n$ by $n-1$ on both sides:

**eq 2:** $T(n-1) = 2T(n-2)+c$ where $c = 4$

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

$T(n) = 2(2T(n-2)+c)+c$

= $4T(n-2)+3c$

= $4(2T(n-3)+c)+3c$

= $8T(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) = 2^kT(n-k)+(2^k-1)c \space$

where $k$ 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 \;\;\;\;\;\; \color{red} k \color{red}= \color{red}1$

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

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

$\cdots$

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

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

$= 2^{n-1}+ c2^{n-1}-c$

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

Hence,

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

This means that the `fib(n)`

function is in $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)`

: