government / examples / fibonacci.gov.lisp

@ 69e3ad85cc0f4df2aca759df28acafb505578821 | history


; fibonacci.gov.lisp: the Fibonacci numbers, two ways.

; The definition read straight off: fib(n) = fib(n-1) + fib(n-2). Each call
; makes two more, so the work doubles with every step of n.
(define fib
  (lambda (n)
    (if (< n 2)
        n
        (+ (fib (- n 1)) (fib (- n 2))))))

(fib 20)

; Carrying the last two numbers along instead takes n steps: a and b are
; fib(i-1) and fib(i). loop calls itself as its last act, a tail call, so
; it runs in constant stack space. It is defined inside fast-fib's body,
; where it can see n.
(define fast-fib
  (lambda (n)
    (define loop
      (lambda (i a b)
        (if (== i n)
            b
            (loop (+ i 1) b (+ a b)))))
    (if (== n 0)
        0
        (loop 1 0 1))))

(fast-fib 20)

; The largest Fibonacci number that fits in 64 bits. (fast-fib 93) would
; overflow, which is an error rather than a wrapped-around number.
(fast-fib 92)