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 matravrtta or matrachandas, each line of poetry consists of a fixed number of “beats” (matra), where each light syllable lasts one beat, and each heavy syllable lasts two beats. The formal study of matra–vrtta dates back to the Chandahsastra , written by the scholar Pingala between 600 BCE and 200 BCE. Pingala observed that there are exactly five 4-beat meters: ——, — • •, • — •, • •—, and • • • •. (Here, each “—” represents a long syllable, and each “•” represents a short syllable.)

Although Pingala’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 Virahanka wrote a commentary on Pingala’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 is not 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 Virahanka, 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 Virahanka’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: