Implementing the Fibonacci Numbers

The fibonacci numbers are a sequence of integers defined as follows.

Let F(n) be the n-th fibonacci number, then:

• F(1) = 0
• F(2) = 1
• F(n) = F(n-1) + F(n-2) for all n>2

Thus, the first 10 fibonacci numbers are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Since the definition of the fibonacci numbers is already recursive (using a so called recurrence relation), their recursive implementation is taken as example for recursive programming in a lot of basic programming courses.

The naive approach to write a recursive function calculating the n-th fibonacci number would look like this:

Function fib(n)
   IF n=1 THEN
      RETURN 0
   ELSE IF n=2 THEN
      RETURN 1
   ELSE
      RETURN fib(n-1) + fib(n-2)

Because of the last line of the above code, multiple computations of already computed fibonacci numbers are performed over and over again. To calculate F(5), we need to calculate F(4) and F(3). To calculate F(4) we need to calculate F(3) (again!) and F(2) and so on. For example, in a call of fib(15) the following numbers are calculated:

Fibonacci number	Count of calculations
F(15)	1
F(14)	1
F(13)	2
F(12)	3
F(11)	5
F(10)	8
F(9)	13
F(8)	21
F(7)	34
F(6)	55
F(5)	89
F(4)	144
F(3)	233
F(2)	377
F(1)	233

(By the way, this is a perfect example for practical usage of the fibonacci numbers: Think about the count of calculations and if and why these values look familiar to your eyes :) )

In the following video I'll introduce an iterative approach (implemented recursively!) to calculate the numbers in javascript without redundant computation. The pseudo code looks like this:

Function fib(n)
   IF n=1 THEN
      RETURN 0
   ELSE IF n=2 THEN
      RETURN 1
   ELSE
      RETURN fibInner(n, 3, 1, 0)

Funciton fibInner(n, iter, prev, pprev)

   IF iter=0 THEN

      RETURN prev+pprev

   ELSE

      RETURN fibInner(n, iter+1, prev+pprev, prev)

Here we actually have a function fibInner that gets as its parameters the values of the two previous fibonacci numbers. We are therefore storing the information we need to calculate the next number without the need of calculating them again.

If you are interested in a more detailed explanation or in the javascript implementation, have a look at the video here:

Last but not least, here are some great links to further information about recursion/iteration and how to cope with some problems that can occur when using recursion - taken out from the book Structure and Interpretation of Computer Programs

• (Linear) Recursion and Iteration
• Tree recursion - example featuring the fibonacci numbers

The fibonacci numbers are a very well studied sequence. To see what kind of stuff math gurus do with them, have a look at the wikipedia article.