Most Computer Science students at some point meet up with the Fibonacci Sequence – an interesting application of recursion. Yet there’s more to fibonacci than just 1, 1, 2, 3, 5, 8, 13, …

In 1170 AD, in Italy, was born Leonardo of Pisa, son of Bonaccio. Leonardo grew to be a fine mathematician and is widely regarded as “the best mathematician of the middle ages”. Though he is well known for the Fibonacci ( *he got this nickname from filius Bonacci – son of Bonacci*) sequence, I think that his most important contribution is the advocacy for the use of the Hindu-Arabic numeral system instead of the Roman Numerals. That might well have been one of the things that helped Europe out of the dark ages.

The Hindu-Arabic numeral system advocates the use of different symbols for the digits 0-9. In contrast, Roman numerals use I, II, III, IV, V, VI, VII, VIII, IX and X to represent 1 to 10 which is very impractical: since there’s no 0, it’s quite awkward to do maths and it’s hard to do basic arithmetic with

– – – – – – – – – – – – – – –

**Back to that interesting sequence**

Leonardo used this series to calculate the growth of a rabbit population that started with a pair of rabbits – assumption: a pair takes 1 month to reach maturity and also each time a pair is delivered.

- First month: 1 pair :: A
- Second month: 2 pairs since the rabbits give birth to a pair :: A -> B
- Third month: 3 pairs – the parents deliver again :: A -> C & B
- Fouth month: 5 pairs – the first pair gives birth for the third time and the second pair gives birth for the first time :: A -> D, B -> E, C

Thereby the sequence: Fn = Fn-1 + Fn+1

But here again we can trace the origins of the sequence to much older times:

“The Fibonacci numbers first appeared, under the name

mātrāmeru(mountain of cadence), in the work of the Sanskrit grammarian Pingala (Chandah-shāstra, the Art of Prosody, 450 or 200 BC). Prosody was important in ancient Indian ritual because of an emphasis on the purity of utterance. The Indian mathematician Virahanka (6th century AD) showed how the Fibonacci sequence arose in the analysis of metres with long and short syllables. Subsequently, the Jain philosopher Hemachandra (c.1150) composed a well-known text on these. A commentary on Virahanka’s work by Gopāla in the 12th century also revisits the problem in some detail.” – http://en.wikipedia.org/wiki/Fibonacci_number

and we are still pretty much fascinated by it. An example is the journal: *The Fibonacci Quarterly* which “is meant to serve as a focal point for interest in Fibonacci numbers and related questions, especially with respect to new results, research proposals, challenging problems, and innovative proofs of old ideas” – http://www.engineering.sdstate.edu/~fib/.

To conclude, an example of a simple finonacci recursive program written in python:

def fib(n):

if (n == 0):

return 1

elif (n == 1):

return 1

else:

return (fib(n-1) + fib(n-2))

print fib(30)

There are two things that I find fascinating with the Fibonacci sequence:

(1) For N relatively large,

fib(N+1) = k x fib(N)

and k is, guess what, the golden ratio!

(2) Nature is full of instances of the Fibonacci sequence. If I am not mistaken, petals in a rose are arranged according to the Fibonacci numbers!

Here is an implementation of Fibonacci in Scheme:

(define (fib n)

(if (<= n 1)

1

(+ (fib (- n 1)) (fib (- n 2)))))

It’s hopelessly inefficient!

A much more efficient version is here:

(define (fib n)

(define (fib-aux n a b)

(if (= n 0)

a

(fib-aux (- n 1) b (+ a b))))

(fib-aux n 1 1))

It is much more efficient because it is tail-recursive 🙂