The memoized recursive solution is a good demonstration of how to use memoization to improve recursive function execution time. But it also seriously increases the memory requirements for many algorithms. If the question is "generate the first N numbers in the Fibonacci series", then memoization is a reasonable answer (though still not the fastest) since you actually need to generate and store every value anyways. If the question, instead, is "generate the Nth number in the series", then memoization will require an array of N values, when only 2 (at a time) are needed (which can still be generated recursively, but efficiently):

  (defun fib (n &optional (a 0) (b 1))
    (cond ((zerop n) a)
          (t (fib (1- n) b (+ a b)))))

With tail recursion, that should be as fast as the iterative solution and uses as much memory to store the intermediate values.

Of course, the Fibonacci series also grows incredibly fast, so practically speaking, unless your language supports arbitrarily large integers, you'll never generate even 100 elements of the series.