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 600 BCE and 200 BCE. $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$ ...