4 ms·
IIUIC, the example they give of recursively calculating the Fibonacci series is pretty much _the_ textbook example of how not to use recursion --- it's O(2^n) a
by david-given 11y ago
IIUIC, the example they give of recursively calculating the Fibonacci series is pretty much _the_ textbook example of how not to use recursion --- it's O(2^n) and doesn't use tail calls, which means it's slow and will gobble memory.
Actually calculating the Fibonacci series efficiently in a non-lazy functional language looks surprisingly non-trivial. In Haskell it's pretty simple:
http://blog.srinivasan.biz/software/fibonacci-numbers-the-slow-way-or-the-fast-and-lazy-way http://blog.srinivasan.biz/software/fibonacci-numbers-the-sl...
- cousin_it 11y agoHere's a page about calculating Fibonacci numbers efficiently: http://www.nayuki.io/page/fast-fibonacci-algorithms http://www.nayuki.io/page/fast-fibonacci-algorithms The method you linked to is listed there as "Dynamic programming (slow)".
- cygx 11y agoThe Haskell code in question: fibs = 1:1:zipWith (+) fibs (tail fibs) It's also a common showcase for Perl6 lazy lists: my @fibs = 1, 1, * + * ... *;
- nanny 11y agoSeriously: Scheme is guaranteed to have tail-call replacement, the author should really take advantage of that. Here's one that does: (define (fib-tco n) (let loop ((x 0) (y 1) (num n)) (if (zero? n) x (loop y (+ x y) (- num 1))))) Try getting the 1000th Fibonacci number which each of these. Also, what's with the dangling parentheses?
- philh 11y ago> Actually calculating the Fibonacci series efficiently in a non-lazy functional language looks surprisingly non-trivial. I don't know if you'd count it as trivial, but one could do def fib(n, a=0, b=1, c=2): if n <= 1: return n if n == c: return a+b return fib(n, b, a+b, c+1) which beats the Haskell lazy list in being O(1) space (except Python doesn't eliminate tail calls).
- Nemcue 11y agoFurther more, it's very hard to see the merit of FP strictly from Fibonacci. I'd go so far as to assume most of us don't spend all day coding anything close to Fibonacci series.