Fibonacci Numbers—Recursive Approach

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 $m\overset{-}{a}tr\overset{-}{a}v\underset{.}{r}tta$ or $m\overset{-}{a}tr\overset{-}{a}chandas$, each line of poetry consists of a fixed number of “beats” ($m\overset{-}{a}tr\overset{-}{a}$), where each light syllable lasts one beat, and each heavy syllable lasts two beats. The formal study of $m\overset{-}{a}tr\overset{-}{a}v\underset{.}{r}tta$ dates back to the $Chanda\underset{.}{h}ś\overset{-}{a}stra$, written by the scholar $Pi\overset{.}{n}gala$ between 600BCE and 200BCE. $Pi\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 $Pi\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 $Virah\overset{-}{a}\underset{.}{n}ka$ wrote a commentary on $Pi\overset{.}{n}gala’s$ work, in which he observed that the number of meters with $n$ beats is the sum of the number of meters with $(n − 2)$ beats and the number of meters with $(n − 1)$ beats. In more modern notation, $Virah\overset{-}{a}\underset{.}{n}ka’s$ observation implies a recurrence for the total number $M(n)$ of $n$-beat meters:

$$M(n) = M(n − 2) + M(n − 1)$$

It isn’t hard to see that $M(0) = 1$ (there is only one empty meter) and $M(1) = 1$ (the only one-beat meter consists of a single short syllable). The same recurrence reappeared in Europe about 500 years after $Virah\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 $Virah\overset{-}{a}\underset{.}{n}ka’s$ recurrence, but with different base cases:

$$F_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) = F_{n+1}$ for all $n$.

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: