@ b16190dee4ae781544f8119bec44f00f5224c810 | 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)