5 ms·
If you use recurssion for Fibbonacci, you do not understand neither recurrsion nor Fibbonacci.
by rimliu 6y ago
If you use recurssion for Fibbonacci, you do not understand neither recurrsion nor Fibbonacci.
- WalterBright 6y ago"You, Sir, are employing a double negative." -- Mr. Spock
- rimliu 6y agoAm I?
- WalterBright 6y agoIt's "not understand either" or "understand neither".
- c17r 6y ago“You understand neither recursion nor Fibonacci” Or “You do not understand recursion nor Fibonacci”
- egman_ekki 6y agoAin't nobody got time for that.
- WalterBright 6y agoAin't nobody got no time for that. FTFY
- elcomet 6y agoThat'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.