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

Get hands-on with 1200+ tech skills courses.