# Fibonacci numbers (Lisp)

### From LiteratePrograms

**Other implementations**: ALGOL 68 | Alice ML | bc | C | C Plus Plus templates | dc | E | Eiffel | Erlang | Forth | FORTRAN | Haskell | Hume | Icon | Java | JavaScript |**Lisp**| Logo | Lua | Mercury | OCaml | occam | Oz | Pascal | PIR | PostScript | Python | Ruby | Scala | Scheme | Sed | sh | sh, iterative | Smalltalk | T-SQL | Visual Basic .NET

The Fibonacci numbers are the integer sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, ..., in which each item is formed by adding the previous two. The sequence can be defined recursively by

- 1 \\ \end{cases} ."/>

Fibonacci number programs that implement this definition directly are often used as introductory examples of recursion. However, many other algorithms for calculating (or making use of) Fibonacci numbers also exist.

The Fibonacci numbers in Common Lisp:

<<fib.lisp>>=fib fib-trec printfib main

## Contents |

## Simple Recursive

This is a simple recursive implementation.

<<fib>>=(defunfib(n)"Simple recursive Fibonacci number function"(if(< n 2)n(+(fib(- n 1))(fib(- n 2)))))

This simple implementation takes exponential time to compute a Fibonacci number. When we trace the execution, we can see what's happening:

(trace fib)

(FIB) * (fib 4) 0: (FIB 4) 1: (FIB 3) 2: (FIB 2) 3: (FIB 1) 3: FIB returned 1 3: (FIB 0) 3: FIB returned 0 2: FIB returned 1 2: (FIB 1) 2: FIB returned 1 1: FIB returned 2 1: (FIB 2) 2: (FIB 1) 2: FIB returned 1 2: (FIB 0) 2: FIB returned 0 1: FIB returned 1 0: FIB returned 3 3

`(FIB 1)`

and `(FIB 0)`

are calculated multiple times. You should have a look at the traces of `(FIB 5)`

and `(FIB 6)`

to see how fast it grows.

## Tail-recursive

Here is a faster version that uses a local helper function which gets the last two numbers passed and is also tail-recursive:

<<fib-trec>>=(defunfib-trec(n)"Tail-recursive Fibonacci number function"(labels((calc-fib(n a b)(if(= n 0)a(calc-fib(- n 1)b(+ a b)))))(calc-fib n 0 1)))

## Comparison

We can easily verify that this is much faster:

(time(fib 40))

Evaluation took: 17.793 seconds of real time 17.562605 seconds of user run time 0.072149 seconds of system run time 0 page faults and 48 bytes consed. 102334155

(time(fib-trec 40))

Evaluation took: 0.0 seconds of real time 7.e-6 seconds of user run time 4.e-6 seconds of system run time 0 page faults and 48 bytes consed. 102334155

## Test driver

This function prints the Fibonacci numbers in the range from *start* to *end* (inclusive).

<<printfib>>=(defunprintfib(start end)(format t "(fib-trec ~D)=~D~%" start(fib-trec start))(if(< start end)(printfib(+ start 1)end)))

When calling *printfib*, the output should be:

(fib-trec 1)=1

(fib-trec 2)=1

(fib-trec 3)=2

(fib-trec 4)=3

(fib-trec 5)=5

...

(fib-trec 30)=832040

<<main>>=(printfib 1 30)

Download code |