6 ms·

Looped algorithms generally outperform recursive algorithms.

by jbluepolarbear 6y ago

beaconstudios 6y ago
does that hold for languages/compilers with tail call optimisation?
- hydroxideOH- 6y ago
  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.
- jbluepolarbear 6y ago
  Tail calling is basically looping and why I said generally.
- desertrider12 6y ago
  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.
  - adrianN 6y ago
    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.
  - iamevn 6y ago
    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)])))
    - desertrider12 6y ago
      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.
  - kaba0 6y ago
    Haskell is not that clever (or at least it was not a year ago). The memoized version is much much faster.
exporectomy 6y ago
And don't cause stack overflows in normal operation. I've run into that before and now avoid recursion.
Tyr42 6y ago
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)
- ThatGeoGuy 6y ago
  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.7143&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54...
  - jbluepolarbear 6y ago
    That was a really good short read.
didibus 6y ago
Recursion is a form of looping. I think it's more clear if you say imperative algorithms.
- arcturus17 6y ago
  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?
  - 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 ago
      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!
      - 6y ago

Looped algorithms generally outperform recursive algorithms.

beaconstudios 6y ago

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

hydroxideOH- 6y ago
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.
jbluepolarbear 6y ago
Tail calling is basically looping and why I said generally.
desertrider12 6y ago
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.
- adrianN 6y ago
  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.
- iamevn 6y ago
  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)])))
  - desertrider12 6y ago
    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.
- kaba0 6y ago
  Haskell is not that clever (or at least it was not a year ago). The memoized version is much much faster.

exporectomy 6y ago

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

Tyr42 6y ago

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)

ThatGeoGuy 6y ago
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.7143&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54...
- jbluepolarbear 6y ago
  That was a really good short read.

didibus 6y ago

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

arcturus17 6y ago
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?
- 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 ago
    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!
    - 6y ago