4 ms·

>Would suggest instead something like Honestly, I think your version is less clear on its own in that it obscures the main point of that particular statement:

>Would suggest instead something like Honestly, I think your version is less clear on its own in that it obscures the main point of that particular statement: when it's best to consider recursion instead of nested loops. In other words, the original is a statement about why or when to use recursion, while yours is a statement about how recursion helps. It's great complementary background though.

AstralStorm 9y ago
Simple answer: never unless you happen to have unbounded call stack depth. Stack sizes are limited on all architectures I'm aware of, on some even drastically. And stack overflows are very tricky to handle correctly. Unless you want to limit recursion depth manually or have proven that overflow cannot happen with a formal proof. (With your bounded stack size.) In all other cases, explicit data structure (not necessarily a stack) will both make debugging easier and additionally uncover performance problems you haven't thought about.
- unclebucknasty 9y ago
  Well, I wasn't offering an opinion as to when recursion should be used--merely pointing out that the GP's proposed change didn't hold the same meaning as the original. >never unless you happen to have unbounded call stack depth. But, since you mention it, I'd have to disagree with your assertion. It's not just about call stack-depth or artificial limitations. There are plenty of use-cases wherein the search-space-depth itself is naturally bound, but unknown/variable down any particular path (e.g. category hierarchies). And, yes, we can impose reasonable "manual" limitations on still more use-cases to expand this universe even further. Using recursion in these cases is far more elegant than nested loops.
  - AstralStorm 9y ago
    That falls under "proved it cannot happen with a formal proof". If you didn't actually prove it you're playing with fire. Funny thing is that proofs over recursive functions are either very easy or terribly involved. Also it is a false dichotomy. Nested loops are not the only option.
- imtringued 9y ago
  All physical machines have limited memory and therefore limited stack and heap sizes. Getting a stackoverflow or running out of memory are the same thing. So going from the stack to the heap doesn't mean you don't have to formally verify it.
jerf 9y ago
I'm open to rewording, but my core complaint is that the text is factually incorrect; the way you iterative-a-tize a recursive algorithm is not with nested for loops. I wouldn't even say it's good didactically; it reinforces the very wrong ideas that we're trying to sweep away at exactly the wrong time. I think it's also helpful to explicitly see recursion as using the fact that our programming language happens to have a stack lying around to do stack things, instead of implementing our own stack. It also tends to at least bring the things AstralStorm is discussing to mind, when you think about it that way, namely, that you have to consider the limitations of your local call stack before you go too crazy with this stuff. Recursion algorithms that involve more than O(log n)-deep calls must be eyed very carefully. And O(n) certainly comes up a lot; best avoided if you don't have a tail-recursion-optimizing language.
- unclebucknasty 9y ago
  >the way you iterative-a-tize a recursive algorithm is not with nested for loops. >it reinforces the very wrong ideas that we're trying to sweep away at exactly the wrong time. I think I'm missing something. Recursion, by definition, is iterative--at least in terms of it involving the repetitive application of some operation(s). Maybe I'm misinterpreting something, but I've most heavily used it in backtracking and decomposition problems which otherwise couldn't be solved as elegantly. So, my experience has not been so much one of "iterative-a-tizing" a recursive algorithm, but "recursive-a-tizing" an iterative one. What applications/ideas are we trying to sweep away? >I think it's also helpful to explicitly see recursion as using the fact that our programming language happens to have a stack lying around to do stack things Completely agree with this and the larger concept of understanding how idioms you're using actually work under the hood. Some languages make certain constructs easily accessible and very easy to misuse (e.g. ThreadLocals). The simplicity of their interfaces belies the massive trouble that can easily be created, absent an understanding of their implementations.
  - jerf 9y ago
    "I think I'm missing something. Recursion, by definition, is iterative--at least in terms of it involving the repetitive application of some operation(s)." In this context, "recursive" means "decomposing the problem with function calls", as the post is discussing, and "iterative" is a sloppy-catch all term for "doing things with for loops and such". It's sloppy because you can't just say "doing things without calling functions" because there are of course non-"recursive" ways of calling functions in an "iterative" routine (for a simple example, calling a logging function). Please pardon the sloppy terminology here; since we're discussing beginner concepts here it's hard to avoid. (For instance, most beginning recursion discussions focus on a function that calls itself, but you can have recursion where A calls B which calls A etc., or more complicated routines for things like traversing a parse tree, where the function called depends on node type; I've witnessed a student claim that those can't be recursive because recursive functions are only recursive when they call themselves.)

AstralStorm 9y ago

Simple answer: never unless you happen to have unbounded call stack depth. Stack sizes are limited on all architectures I'm aware of, on some even drastically. And stack overflows are very tricky to handle correctly. Unless you want to limit recursion depth manually or have proven that overflow cannot happen with a formal proof. (With your bounded stack size.) In all other cases, explicit data structure (not necessarily a stack) will both make debugging easier and additionally uncover performance problems you haven't thought about.

unclebucknasty 9y ago
Well, I wasn't offering an opinion as to when recursion should be used--merely pointing out that the GP's proposed change didn't hold the same meaning as the original. >never unless you happen to have unbounded call stack depth. But, since you mention it, I'd have to disagree with your assertion. It's not just about call stack-depth or artificial limitations. There are plenty of use-cases wherein the search-space-depth itself is naturally bound, but unknown/variable down any particular path (e.g. category hierarchies). And, yes, we can impose reasonable "manual" limitations on still more use-cases to expand this universe even further. Using recursion in these cases is far more elegant than nested loops.
- AstralStorm 9y ago
  That falls under "proved it cannot happen with a formal proof". If you didn't actually prove it you're playing with fire. Funny thing is that proofs over recursive functions are either very easy or terribly involved. Also it is a false dichotomy. Nested loops are not the only option.
imtringued 9y ago
All physical machines have limited memory and therefore limited stack and heap sizes. Getting a stackoverflow or running out of memory are the same thing. So going from the stack to the heap doesn't mean you don't have to formally verify it.

jerf 9y ago

I'm open to rewording, but my core complaint is that the text is factually incorrect; the way you iterative-a-tize a recursive algorithm is not with nested for loops. I wouldn't even say it's good didactically; it reinforces the very wrong ideas that we're trying to sweep away at exactly the wrong time. I think it's also helpful to explicitly see recursion as using the fact that our programming language happens to have a stack lying around to do stack things, instead of implementing our own stack. It also tends to at least bring the things AstralStorm is discussing to mind, when you think about it that way, namely, that you have to consider the limitations of your local call stack before you go too crazy with this stuff. Recursion algorithms that involve more than O(log n)-deep calls must be eyed very carefully. And O(n) certainly comes up a lot; best avoided if you don't have a tail-recursion-optimizing language.

unclebucknasty 9y ago
>the way you iterative-a-tize a recursive algorithm is not with nested for loops. >it reinforces the very wrong ideas that we're trying to sweep away at exactly the wrong time. I think I'm missing something. Recursion, by definition, is iterative--at least in terms of it involving the repetitive application of some operation(s). Maybe I'm misinterpreting something, but I've most heavily used it in backtracking and decomposition problems which otherwise couldn't be solved as elegantly. So, my experience has not been so much one of "iterative-a-tizing" a recursive algorithm, but "recursive-a-tizing" an iterative one. What applications/ideas are we trying to sweep away? >I think it's also helpful to explicitly see recursion as using the fact that our programming language happens to have a stack lying around to do stack things Completely agree with this and the larger concept of understanding how idioms you're using actually work under the hood. Some languages make certain constructs easily accessible and very easy to misuse (e.g. ThreadLocals). The simplicity of their interfaces belies the massive trouble that can easily be created, absent an understanding of their implementations.
- jerf 9y ago
  "I think I'm missing something. Recursion, by definition, is iterative--at least in terms of it involving the repetitive application of some operation(s)." In this context, "recursive" means "decomposing the problem with function calls", as the post is discussing, and "iterative" is a sloppy-catch all term for "doing things with for loops and such". It's sloppy because you can't just say "doing things without calling functions" because there are of course non-"recursive" ways of calling functions in an "iterative" routine (for a simple example, calling a logging function). Please pardon the sloppy terminology here; since we're discussing beginner concepts here it's hard to avoid. (For instance, most beginning recursion discussions focus on a function that calls itself, but you can have recursion where A calls B which calls A etc., or more complicated routines for things like traversing a parse tree, where the function called depends on node type; I've witnessed a student claim that those can't be recursive because recursive functions are only recursive when they call themselves.)