Fibonacci numbers (Lisp)

From LiteratePrograms
Jump to: navigation, search
Other implementations: bc | C | C Plus Plus templates | dc | E | Forth | FORTRAN | Haskell | Icon | Java | JavaScript | Lisp | Lua | occam | Oz | PIR | Prolog | Python | Sed | sh | sh, iterative | 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


 F(n) =
 \begin{cases}
   0             & n = 0 \\
   1             & n = 1 \\
   F(n-1)+F(n-2) & n > 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

[edit] 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.

[edit] 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)))

[edit] 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

[edit] 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
hijacker
hijacker
hijacker
hijacker