3 ms·
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")
by elcomet 6y ago
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")
- rimliu 6y agoThere are lots of thing you can, but you should not.
- smabie 6y agoWhat'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.
- Jtsummers 6y agoThe 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.
- jlokier 6y agoIf 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.