That's a bold claim. You can very much solve Fibonacci with recursion efficiently. It's just not in the naive way. (You can look up "accumulator")

There are lots of thing you can, but you should not.

What's wrong with a memoized recursive solution? Or a DP tail recursive solution? Tail recursive solutions are less buggy, easier to code, and easier to write than iterative ones. And they're much easier to prove the correctness of as well.

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.

If the question is "generate the Nth number in the series", I would be inclined to suggest a closed-form solution that returns in O(1) time (assuming regular size integers), no iteration required.

"You, Sir, are employing a double negative." -- Mr. Spock

Am I?

It's "not understand either" or "understand neither".

“You understand neither recursion nor Fibonacci”

Or

“You do not understand recursion nor Fibonacci”

Ain't nobody got time for that.

Ain't nobody got no time for that.

FTFY