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

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:

$\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):