Hacker News Reader

Comment by david-given | Hacker News Reader

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

View on HN

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

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.

Haskell does this, too.

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

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?

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

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

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

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

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.

Reply on news.ycombinator.com