Fibonacci Numbers—Recursive Approach

Let's solve the Fibonacci numbers using the recursive approach with memoization.

Origins of recursion

One of the earliest examples of recursion arose in India more than 2000 years ago, in the study of poetic meter or prosody. Classical Sanskrit poetry distinguishes between two types of syllables (aksara): light (laghu) and heavy (guru). In one class of meters, variously called matravr.ttam\overset{-}{a}tr\overset{-}{a}v\underset{.}{r}tta or matrachandasm\overset{-}{a}tr\overset{-}{a}chandas, each line of poetry consists of a fixed number of “beats” (matram\overset{-}{a}tr\overset{-}{a}), where each light syllable lasts one beat, and each heavy syllable lasts two beats. The formal study of matravr.ttam\overset{-}{a}tr\overset{-}{a}-v\underset{.}{r}tta dates back to the Chandah.sˊastraChanda\underset{.}{h}ś\overset{-}{a}stra, written by the scholar Pin.galaPi\overset{.}{n}gala between 600 BCE and 200 BCE. Pin.galaPi\overset{.}{n}gala observed that there are exactly five 4-beat meters: ——, — • •, • — •, • •—, and • • • •. (Here, each “—” represents a long syllable, and each “•” represents a short syllable.)

Although Pin.galasPi\overset{.}{n}gala’s text hints at a systematic rule for counting meters with a given number of beats, it took about a millennium for that rule to be stated explicitly. In the 7th-century CE, another Indian scholar named Virahan.kaVirah\overset{-}{a}\underset{.}{n}ka wrote a commentary on Pin.galasPi\overset{.}{n}gala’s work, in which he observed that the number of meters with nn beats is the sum of the number of meters with (n2)(n − 2) beats and the number of meters with (n1)(n − 1) beats. In more modern notation, Virahan.kasVirah\overset{-}{a}\underset{.}{n}ka’s observation implies a recurrence for the total number M(n)M(n) of nn-beat meters:

M(n)=M(n2)+M(n1)M(n) = M(n − 2) + M(n − 1)

It is not hard to see that M(0)=1M(0) = 1 (there is only one empty meter) and M(1)=1M(1) = 1 (the only one-beat meter consists of a single short syllable). The same recurrence reappeared in Europe about 500 years after Virahan.kaVirah\overset{-}{a}\underset{.}{n}ka, in Leonardo of Pisa’s 1202 treatise Liber Abaci, one of the most influential early European works on “algorism.” In full compliance with Stigler’s Law of Eponymy, the modern Fibonacci numbers are defined using Virahan.kasVirah\overset{-}{a}\underset{.}{n}ka’s recurrence, but with different base cases:

Fn={ 0 if n=0 1 if n=1Fn1+Fn2otherwiseF_n=\begin{cases} & \text{ 0 } \hspace{1.87cm} if\space n=0 \\ & \text{ 1 } \hspace{1.87cm} if\space n=1\\ & F_{n-1} + F_{n-2} \hspace{0.4cm} otherwise \end{cases}

In particular, we have M(n)=Fn+1M(n) = F_{n+1} for all nn.

Backtracking can be slow

The recursive definition of Fibonacci numbers immediately gives us a recursive algorithm for computing them. Here is the same algorithm written in pseudocode:

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy