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