Inefficient Recursion: Fibonacci Numbers

Let’s study a scenario where recursion introduces inefficiency by repeatedly calculating the same value.

We'll cover the following

Inefficient recursion

Here is another classic example of recursion – calculating the nthn^{th} Fibonacci number. It turns out that this is hopelessly inefficient using pure recursion, but we will also look at a useful technique to alleviate the problem.

If you are not familiar with the Fibonacci series, it is an infinite series of numbers defined as follows:

F0F_0 = 0
F1F_1 = 1
F2F_2 = F1F_1 + F0F_0 = 1
F3F_3 = F2F_2 + F1F_1 = 2

F(n)F_{(n)} = F(n1)F_{(n-1)} + F(n2)F_{(n-2)}

In other words, each element is the sum of the two previous elements. Here are the first few values of the series:

0,1,1,2,3,5,8,13,21...0, 1, 1, 2, 3, 5, 8, 13, 21...

This can obviously be calculated recursively, as shown below.

Get hands-on with 1200+ tech skills courses.