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 in Common Lisp:

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

Contents 1 Simple Recursive 2 Tail-recursive 3 Comparison 4 Test driver

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)

Download code