3 different (fib n) implementations.

3 fibs

;;; Works in DrRacket Pretty Big language

(define fibRecursive (lambda (n) (cond ((= n 0) 1) 
                                       ((= n 1) 1) 
                                       (else (+ (fibRecursive (- n 1)) (fibRecursive (- n 2)))))))

(define range (lambda (n m) (cond ((= n m) (list n)) (else (cons n (range ((if (< n m) + -) n 1) m))))))
(define fibLinear (lambda (n) (car (foldr (lambda (foo pair) (list (cadr pair) (+ (car pair) (cadr pair)))) '(0 1) (range 0 n)))))

(define square (lambda (x) (* x x)))
(define pow (lambda (base exp) (cond ((= exp 0) 1)
                                     ((= exp 1) base)
                                     ((even? exp) (square (pow base (/ exp 2))))
                                     (else (* base (square (pow base (/ (- exp 1) 2))))))))
(define phi (/ (+ 1 (sqrt 5)) 2)) ; Finite floating point precision renders fibLog inaccurate for large n
(define fibLog (lambda (n) (inexact->exact (round (/ (pow phi (+ n 1)) (sqrt 5))))))

(map fibRecursive (range 0 10))
(map fibLinear (range 0 10))
(map fibLog (range 0 10))