Fibonacci
The Fibonacci sequence of numbers was described in a mathematics book by Leonardo da Pisa (Fibonacci) called Liber Abaci. The n-th element of the sequence represents the number of pairs of rabbits at the start of the n-th month, beginning with a single pair, given that in every month each pair bears a new pair which becomes productive from the second month on. It is a common example used in education to teach recursion.

Here are the first 14 Fibonacci numbers, starting with F(0):
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...
and various Common Lisp implementations for the computation of the nth element of the sequence, structured similarly to the Factorial page:

(defun fib (n) "Naive recursive computation of the nth element of the Fibonacci sequence" (check-type n (integer 0 *)) (if (< n 2) n (+ (fib (1- n)) (fib (- n 2)))))

(defun fib (n) "Tail-recursive computation of the nth element of the Fibonacci sequence" (check-type n (integer 0 *)) (labels ((fib-aux (n f1 f2) (if (zerop n) f1 (fib-aux (1- n) f2 (+ f1 f2))))) (fib-aux n 0 1)))

This loop-based implementation probably written by Nicolas Neuss (my.name@iwr.uni-heidelberg.de):

(defun fib (n) "loop-based iterative computation of the nth element of the Fibonacci sequence" (check-type n (integer 0 *)) (loop for f1 = 0 then f2 and f2 = 1 then (+ f1 f2) repeat n finally (return f1)))

(defun fib (n) "do-based iterative computation of the nth element of the Fibonacci sequence" (check-type n (integer 0 *)) (do ((i n (1- i)) (f1 0 f2) (f2 1 (+ f1 f2))) ((= i 0) f1)))

(defun fib (n) "CPS computation of the nth element of the Fibonacci sequence" (check-type n (integer 0 *)) (labels ((fib-aux (n k) (if (zerop n) (funcall k 0 1) (fib-aux (1- n) (lambda (x y) (funcall k y (+ x y))))))) (fib-aux n #'(lambda (a b) a))))
It is worth mentioning that the initial (lambda (a b) a), or λab.a in lambda calculus notation, is one of the two Church booleans: true.

You can use multiple values for a truly recursive implementation:

(defun fib (n) (labels ((fib2 (n) (cond ((= n 0) (values 1 0)) (t (multiple-value-bind (val prev-val) (fib2 (- n 1)) (values (+ val prev-val) val)))))) (nth-value 0 (fib2 n))))
Of course, this is in some sense equivalent to the CPS version, but with the continuation left implicit. (Author: Drew McDermott, firstname.lastname@yale.edu)

A "successive squaring" method suggested in Structure and Interpretation of Computer Programs, which runs in a logarithmic number of steps:

(defun fib (n) "Successive squaring method from SICP" (check-type n (integer 0 *)) (labels ((fib-aux (a b p q count) (cond ((= count 0) b) ((evenp count) (fib-aux a b (+ (* p p) (* q q)) (+ (* q q) (* 2 p q)) (/ count 2))) (t (fib-aux (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- count 1)))))) (fib-aux 1 0 0 1 n)))
Note that the "clever algorithm" mentioned but not cited in SICP is described in an "EWD note" entitled In honour of Fibonacci by Edsger Wybe Dijkstra.

Another successive squaring method based on these formulas: F(2n-1)=F(n)^2+F(n-1)^2, F(2n)=(2F(n-1)+F(n))*F(n). See the end of this section from the Wikipedia article, or see the same EWD note as above, In honour of Fibonacci by Edsger Wybe Dijkstra.

(defun fib (n) (if (< n 2) n (if (oddp n) (let ((k (/ (1+ n) 2))) (+ (expt (fib k) 2) (expt (fib (1- k)) 2))) (let* ((k (/ n 2)) (fk (fib k))) (* (+ (* 2 (fib (1- k))) fk) fk)))))

And now for something completely different, a generator version, inspired by a Python snippet.

Python Lisp Ruby Javascript
def fib(): a, b = 0, 1 while 1: yield a a, b = b, a+b
(let ((a 0) (b 1)) (defun fib () (prog1 a (psetf a b b (+ a b)))))
def make_fib() a = 0; b = 1 lambda { v = a a, b = b, a + b v } end
var fib; ( function (){ var a=0; var b=1; fib=function (){ b=a+(a=b); return a; } })();
Upon successive calls, (fib) will return the next number in the sequence. JavaScript version by Cosmin Branescu, cosmin.branescu@info.uvt.ro.

;; Taken from Winston's Lisp, 3rd edition, this is a tail-recursive version, w/o an auxiliary function (defun fib (n &optional (i 1) (previous-month 0) (this-month 1)) (if (<= n i) this-month (fib n (+ 1 i) this-month (+ this-month previous-month))))

;;;Original code by Arnold Schoenhage, ;;;translated to Scheme by Bradley J. Lucier (2004), ;;;and adapted to Common Lisp by Nicolas Neuss. (defun fast-fib-pair (n) "Returns f_n f_{n+1}." (case n ((0) (values 0 1)) ((1) (values 1 1)) (t (let ((m (floor n 2))) (multiple-value-bind (f_m f_m+1) (fast-fib-pair m) (let ((f_m^2 (* f_m f_m)) (f_m+1^2 (* f_m+1 f_m+1))) (if (evenp n) (values (- (* 2 f_m+1^2) (* 3 f_m^2) (if (oddp m) -2 2)) (+ f_m^2 f_m+1^2)) (values (+ f_m^2 f_m+1^2) (- (* 3 f_m+1^2) (* 2 f_m^2) (if (oddp m) -2 2))))))))))

;; Fibonacci - Binet's Formula (defun fib (n) (* (/ 1 (sqrt 5)) (- (expt (/ (+ 1 (sqrt 5)) 2) n) (expt (/ (- 1 (sqrt 5)) 2) n))))

or

(defun fib (n) (/ (- (expt (/ (+ 1 (sqrt 5)) 2) n) (expt (/ (- 1 (sqrt 5)) 2) n)) (sqrt 5)))

and even easier

(defun fib (n) (prog1 (round (/ (expt (/ (+ 1 (sqrt 5)) 2) n) (sqrt 5)))))

Q: In the Winston & Horn book, n for the two above functions is n+1. Is there some reason for NOT having e.g.
(expt (/ (- 1 (sqrt 5)) 2) (+ n 1))) ?
A: Some authors still use a deprecated definition of the Fibonacci sequence, the one that begins with 1, 1 instead of 0, 1. Please see the definition and especially the closed form. Also, most books that touch on this topic (Donald Knuth's TAOCP for instance).

Q: Do we have any reason to keep the first implementation instead of the second one based on the Binet formula? --Cornel

Caution: Due to limitations in floating-point representation precision, this last version works - (truncate (fib n)) is correct - only for n < 32.
From that point on, the error rises exponentially approximately like this: new_error = old_error * (5 / 3)
So, if for n = 32 the error is 1.25, for n = 99 the error is 4.2221247E14. I determined this using CLISP 2.33.2 under GNU Linux on IA32.
This can be improved by using 5.0d0 instead of 5, which ensures the use of double-float. CLISP 2.33.2 computes correct values (using (round (fib n)) for n ≤ 75.