This is entirely orthogonal to benchmarking, but I thought I'd point out how memoization is a huge win for the recursive Fibonacci:
arc> (defmemo fib (n) (if (< n 2) 1 (+ (fib (- n 1)) (fib (- n 2)))))
#<procedure>
arc> (time (fib 10000))
time: 957 msec.
...many digits of output omitted...
For those unfamililar with memoization, it makes the function magically remember the results for previous calls. So once you've computed (fib 100), for instance, subsequent calls to (fib 100) return the memoized value immediately. Obviously this only makes sense for functions that depend only on their arguments and don't have side effects. (You pay a space cost, of course, to hold all these results.)
(Even with memoization, this is a silly way to compute Fibonacci numbers, but I think it's an interesting demonstration.)
