*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 *n*th 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))))

*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))))

`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)))

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 make_fib()
a = 0; b = 1
lambda {
v = a
a, b = b, a + b
v
}
end
```

`cosmin.branescu@info.uvt.ro`.

*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))))

*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))))))))))

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

or

and even easier

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.