Hacker News Reader

Comment by rectang | Hacker News Reader

Pro tip: the classic recursive approach to implementing the Fibonacci sequence exhibits eye-wateringly poor performance.

View on HN

I've always hated how that's used as an example of recursive programming in early programming education. Invariably, students try a large n, get a stack overflow and conclude that recursion is inefficient, leads to mysterious errors, and must be avoided.

Fibonacci is generally more likely to take forever than stack overflow.

...which makes it a classic exercise for teaching memoization!

And now your memory usage will grow eye-wateringly large. Instead, convert the algorithm to be iterative or at least tail-recursive and it will be faster than both the naive and memoized versions!

Or use the closed-form solution.

The "closed-form solution" is slower than standard method. It just uses arbitrary-precision fractional arithmetic (square root, exponentiation, division) instead of arbitrary-precision integer arithmetic (exponentiation of a 2x2 integer matrix).

The best solution is to use the O(log n) time exponentiation of a matrix, which is fast enough to be constant.

Looped algorithms generally outperform recursive algorithms.

does that hold for languages/compilers with tail call optimisation?

At least for Racket, which does have TCO, the for-loop is really a macro for a tail recursive loop. I'm not sure about other languages with more aggressive optimization though.

Tail calling is basically looping and why I said generally.

This isn't really related to your question, but I don't think tail calls could help for Fibonacci since f(n) branches to two calls, f(n-1) and f(n-2). And each of those branches into 2. So it can't be done in a finite stack area with naive recursion.

The compiler would either have to memoize, or be extremely clever and start at the base case (0, 1) and then transform the code to use the 2x2 matrix exponentiation. I wouldn't have been suprised if GHC haskell was that clever, but even with -O2 "print $ fibb 10000" isn't terminating.

If you replaced the recursion with loops but implemented the same algorithm you'd just have to manage a stack on the heap. I don't think that would be faster.

Wouldn't this be the recursion version with tail calls?

  (define/contract (fib n)
    (-> nonnegative-integer? nonnegative-integer?)
    (let fib-recur ([i 1] [curr 1] [prev 0])
      (cond [(= i n) curr]
            [else (fib-recur (+ i 1) 
                             (+ curr prev) 
                             curr)])))

That's pretty much what I meant by the matrix exponentiation method - applying the map (a, b) -> (a+b, a) repeatedly. Your function definitely uses tail calls, but I was just trying to say more than tail call optimization is needed to transform the trivial recursive version

fibb 0 = 0

fibb 1 = 1

fibb n = + (fibb (- n 1)) (fibb (- n 2))

into that, or any O(n) version.

Haskell is not that clever (or at least it was not a year ago). The memoized version is much much faster.

And don't cause stack overflows in normal operation. I've run into that before and now avoid recursion.

Goto based algorithms generally outperform looped algorithms.

(They're just more general, you can always implement a loop based algorithm using gotos, but not the other way around)

Not exactly. This is more an artefact of language design.

If you convert everything to continuation passing style, then every function call, tail call, recursion, etc. is just as expensive (and expressive) as a GOTO. This is, incidentally, the main "trick" or lightbulb moment in the classic Cheney on the MTA paper by Henry Baker [1].

Now if we're talking specifically in C, then absolutely! But while this intuition holds for C, it's not always true and doesn't have to be always true.

[1] https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54...

That was a really good short read.

Recursion is a form of looping. I think it's more clear if you say imperative algorithms.

In what sense is recursion a form of looping?

I'm thinking of the memory model for each - one mutates some variables (at least some sort of index, unless you're doing an infinite loop) in a single frame, while the other accumulates function calls and stack frames until you bottom out, then return values are "folded" back up.

Semantically, from a caller's perspective, they can achieve the exact same thing, but aside from that they seem radically different to me - is there anything else that could lead us to say that recursion is a form of looping?

> In computer science, a loop is a programming structure that repeats a sequence of instructions until a specific condition is met.

That's the general definition at least I've always been most aware of. I don't want to claim it is the most common one, cause I don't really have numbers and who is the authority on comp-sci definitons? But I do feel it is at least a somewhat common academic definition for looping.

That would mean that recursion is a form of looping. The distinction between recursion and imperative loops would then be a matter of implementation and exposed programmer interface. Similarly like others have said, goto's can also be used to implement similar loops.

And in that regard, there are variants of recursion as well, such as tail-call recursion which has a similar memory model as what you described and differs only to an imperative loop in the programming interface it exposes.

There's no denying that from that definition they are the same. It's just after you've debugged enough loops and recursions you can't help but think they are quite different!

Well, I don't mean they are the same, they're just different kinds of looping constructs.

Like what you call a loop isn't a loop, its actually a for-loop, or its a while-loop, or a for-each loop, or its an iterator loop, and similarly recursion is just a recursive loop.

At least that's the common taxonomy I know off. So all these are loops, and the ones that involve mutation for the condition to kick in are further grouped as imperative loops.

Reply on news.ycombinator.com