Inefficient Recursion: Fibonacci Numbers

Inefficient recursion

Here is another classic example of recursion – calculating the $n^{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:

$F_0$ = 0
$F_1$ = 1
$F_2$ = $F_1$ + $F_0$ = 1
$F_3$ = $F_2$ + $F_1$ = 2
…
$F_{(n)}$ = $F_{(n-1)}$ + $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...$$

This can obviously be calculated recursively, as shown below.