Fibonacci numbers

Fibonacci numbers can be defined as follows:



We can simply write a Scheme program that does just that:

;; Fib : number -> number
;; calculate Fibonacci number
;; examples:
;; (Fib 0) -> 0
;; (Fib 1) -> 1
;; (Fib 5) -> 5
;; (Fib 10) -> 55
(define (Fib n)
  (cond
    [(< n 2) n]
    [else
     (+
      (Fib (- n 1))
      (Fib (- n 2)))]))

Testing:

> (Fib 0)
0
> (Fib 1)
1
> (Fib 5)
5
> (Fib 10)
55

Here is the trace of (Fib 4), leaving out the uninteresting bits:

(Fib 4)
(+ (Fib 3) (Fib (- 4 2)))
(+ (+ (Fib 2) (Fib (- 3 2))) (Fib (- 4 2)))
(+ (+ (+ (Fib 1) (Fib (- 2 2))) (Fib (- 3 2))) (Fib (- 4 2)))
(+ (+ (+ 1 (Fib 0)) (Fib (- 3 2))) (Fib (- 4 2)))
(+ (+ 1 (Fib 1)) (Fib (- 4 2)))
(+ 2 (Fib 2))
(+ 2 (+ (Fib 1) (Fib (- 2 2)))
(+ 2 (+ 1 (Fib 0)))
3

Compare this with (Fib 3):

(Fib 3)
(+ (Fib 2) (Fib (- 3 2)))
(+ (+ (Fib 1) (Fib (- 2 2))) (Fib (- 3 2)))
(+ (+ 1 (Fib 0)) (Fib (- 3 2)))
(+ 1 (Fib 1))
2

According to the lecture video (see below), in this process, space of Fib(n) is proportional to n, and time is proportional to Fib(n).

Notice that some terms are calculated several times, which indicates code inefficiency. This is clearly not an iterative process, but rather some kind of recursive process.

Can the program be rewritten so, that it does an iterative process, instead of the current recursive process?

Well, how about starting the calculation from 2 and going upwards to n? If n is 0 or 1, the answers are 0 and 1, respectively. Then we use the following definition of Fibs, in which we pass intermediate Fibonacci values as parameters of Fibs, in a recursive fashion:

(define (Fibs a b c n)
  (cond
    [(> c n) b]
    [else (Fibs b (+ a b) (+ c 1) n)]))

In this definition, b is the previous Fibonacci number, a is the Fibonacci number before that, c indicates the order of the current intermediate Fibonacci number, and n indicates the desired order for the Fibonacci number. We seed Fibs with a = 0, b = 1, c = 2, n = n.

Let's try (Fibs 0 1 2 5) in a trace:

(Fibs 0 1 2 5)
(Fibs 1 1 3 5)
(Fibs 1 2 4 5)
(Fibs 2 3 5 5)
(Fibs 3 5 6 5)
5

We can see that the time of Fibs is proportional to n, and the space is proportional to 1. This, therefore, is an iteration process.

Here is the complete program for calculating a Fibonacci number:

;; Fib : number -> number
;; calculate a Fibonacci number
;; e.g. (Fib 4) -> 3
;; e.g. (Fib 10) -> 55
(define (Fib n)
  (cond
    [(< n 2) n]
    [else (Fibs 0 1 2 n)]))
(define (Fibs a b c n)
  (cond
    [(> c n) b]
    [else (Fibs b (+ a b) (+ c 1) n)]))

And (Fib 10) produces 55:

> (Fib 10)
55

If you try out both programs with a really large number (say 100000), you will notice a distinct difference in speed. The second is much faster than the first.

Credits

I have to confess that I didn't come up with the solutions myself.

The first solution was taken from a Lisp tutorial video (lesson 1b of the MIT Lisp video tutorials), and converted into Scheme.

The second solution was taken from Lecture notes about Fibonacci numbers by David Eppstein, professor of Computer Science. The code was written in Python, so I needed to convert from an imperative language notation into the declarative language notation of Scheme, which I had never done before. So there was indeed a, though modest, learning experience in all of this. On that same notes page are some alternative methods you could try.

When in need for a solution, Google is your friend.