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