A Fibonacci number is basically the sum of the previous two.

pos: 0 1 2 3 4 5 6 7  8  9  10 ...
fib: 0 1 1 2 3 5 8 13 21 34 55 ...

Simple but slow version in Scheme:

; Time is of exponential order of N; whereas
; space is of linear order of N
(define (fibslow N)
 (cond ((< N 2) N)
       (else (+ (fibslow (- N 1))
                (fibslow (- N 2))))))

How can we make it faster ?

Warning: reading futher will reveal a faster version.

Fast version in Scheme:

; Time is of linear order of N; whereas
; space is of constant order of N
(define (fibfast N)
 (cond ((< N 2) N)
       (else (fibup N 2 1 0))))

(define (fibup MAX count n-1 n-2)
 (cond ((= MAX count) (+ n-1 n-2))
       (else (fibup MAX (+ 1 count) (+ n-1 n-2) n-1))))

To feel the performance difference, try:

(fibslow 30)

vs.

(fibfast 30)