5 ms·
Pro tip: the classic recursive approach to implementing the Fibonacci sequence exhibits eye-wateringly poor performance.
by rectang 6y ago
Pro tip: the classic recursive approach to implementing the Fibonacci sequence exhibits eye-wateringly poor performance.
- jbluepolarbear 6y agoLooped algorithms generally outperform recursive algorithms.
- beaconstudios 6y agodoes that hold for languages/compilers with tail call optimisation?
- hydroxideOH- 6y agoAt 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.
- jbluepolarbear 6y agoTail calling is basically looping and why I said generally.
- desertrider12 6y agoThis 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.
- adrianN 6y agoIf 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.
- iamevn 6y agoWouldn'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)])))
- desertrider12 6y agoThat'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.
- kaba0 6y agoHaskell is not that clever (or at least it was not a year ago). The memoized version is much much faster.
- exporectomy 6y agoAnd don't cause stack overflows in normal operation. I've run into that before and now avoid recursion.
- Tyr42 6y agoGoto 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)
- ThatGeoGuy 6y agoNot 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.7143&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54...
- jbluepolarbear 6y agoThat was a really good short read.
- didibus 6y agoRecursion is a form of looping. I think it's more clear if you say imperative algorithms.
- arcturus17 6y agoIn 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?
- didibus 6y ago> 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.
- arcturus17 6y agoThere'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!
- 6y ago
- elseweather 6y ago...which makes it a classic exercise for teaching memoization!
- astine 6y agoAnd 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!
- karamazov 6y agoOr use the closed-form solution.
- jacobolus 6y agoThe "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).
- singhrac 6y agoThe best solution is to use the O(log n) time exponentiation of a matrix, which is fast enough to be constant.
- sjburt 6y agoI'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.
- saagarjha 6y agoFibonacci is generally more likely to take forever than stack overflow.