4 ms·

"To iterate is human, recurse devine" -Anon

• eru 16y ago
  Iteration is just a special case.
  • sesqu 16y ago
    When you hit Turing completeness, special casing is no longer a useful exercise.
    • eru 16y ago
      Could you explain what you want to say? I mean, iteration is a special case of recursion. Some languages [1] need special syntax constructs for iteration, like `while' or `for', because their support for recursion is broken. [1] OK, most.
      • sesqu 16y ago
        Iteration: until condition iterate state=update(state). Recursion: recursive(state)=if atomic then state else recursive(refined(state)). condition=atomic, update=refined. One is not a special case of the other; they are just different models for the same process (one is top-down, the other bottom-up). See also objects vs. closures.
        • eru 16y ago
          To quote Structure and Interpretation of Computer Programs (http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html...): [...] most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose ``looping constructs'' such as do, repeat, until, for, and while. The implementation of Scheme we shall consider in chapter 5 does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive. With a tail-recursive implementation, iteration can be expressed using the ordinary procedure call mechanism, so that special iteration constructs are useful only as syntactic sugar.
          • sesqu 16y ago
            Right. Recursion has a problem with stack overflows, but that can sometimes be automatically fixed by turning it into iteration and throwing out the superfluous frames. Which one is the special case now?
            • eru 16y ago
              Why? Iteration. Stacks and stuff are just a way for computers to do some forms of recursion. Recursion itself is just a general mathematical idea. Look at the Natural numbers (http://en.wikipedia.org/wiki/Recursion#Example:_the_natural_numbers http://en.wikipedia.org/wiki/Recursion#Example:_the_natural_...) or dynamic programming (http://en.wikipedia.org/wiki/Recursion#Recursive_optimization http://en.wikipedia.org/wiki/Recursion#Recursive_optimizatio...). Dynamic programming is an interesting case, because in most languages the idiomatic way to express it uses iterative constructs.