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:
represents the fib
function. and 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, and represent the base-cases.
To solve this recurrence, we can simplify it by approximating that . The time that is taken to calculate is greater than the time taken to calculate , so this approximation gives us an upper bound on the total time complexity:
eq 1:
Replacing by on both sides:
eq 2: where
So, we can replace in eq 1 with the value of it in eq 2 to get:
=
=
=
You must have noticed a pattern here, which means that this equation can be written in generic terms.
generic:
where is the number of times that the equation was substituted into. Have a look at the following for a clearer picture:
Let’s consider what value of brings the argument of to the base case of 1. If , then . Next, we substitute k = n - 1 in the expression for . We can now put the generic equation in terms of , the value of which we know is :
Hence,
This means that the fib(n)
function is in , 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)
: