# Fibonacci numbers (Lisp)

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


## Simple Recursive

This is a simple recursive implementation.

<<fib>>=
(defun fib (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>>=
(defun fib-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>>=
(defun printfib (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)