david-given on Once you go functional, you can never go back

Comment on Once you go functional, you can never go back

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-sl...

cygx 11y

The 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, * + * ... *;

cygx 11y

Note that Perl6 uses big integers by default, so this will work even beyond the limit n=92 at which 64-bit integers will overflow.

dllthomas 11y

Haskell does this, too.

codygman 11y

I will admit perl 6 is pretty damn cool. I'll definitely have to look at it soon.

nanny 11y

Seriously: 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?

cousin_it 11y

Here's a page about calculating Fibonacci numbers efficiently:

http://www.nayuki.io/page/fast-fibonacci-algorithms

The method you linked to is listed there as "Dynamic programming (slow)".

philh 11y

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).

wz1000 11y

The front of the list can be garbage collected, so the Haskell version can be O(1) in memory.

dllthomas 11y

Ignoring growth in the size of the output itself (and the intermediary values that are output of earlier stages), anyway...

Nemcue 11y

Further 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.

Comments