5 ms·
"This task can also be solved using iterative solution, but it’s way more complicated because we would have to nest for loops but don’t know how deep they are n
by jerf 9y ago
"This task can also be solved using iterative solution, but it’s way more complicated because we would have to nest for loops but don’t know how deep they are nested. The unknown number of nested loops is a common characteristic of all problems that are recursive in their nature and should give you a hint that recursive solution is required."
Would suggest instead something like
"We could solve this directly by managing our own stack of work done and keeping track of where we are in the problems as we divide them up, but it's easier to take advantage of the fact that the programming language is already providing us a call stack that can do this work for us."
Then, later, you can point out that this also helps with the backtracking solution as the programming language is maintaining the old environments; if you were iteratively managing your own stack you'd also have to backtrack manually.
Because that's how you transform a recursive call into an iterative one, not nested for loops. The general points made in the article still hold up, of course.
- unclebucknasty 9y ago>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 agoSimple 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 agoWell, 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 agoThat 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 agoAll 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 agoI'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.)
- Terr_ 9y ago> it's easier to take advantage of the fact that the programming language is already providing us a call stack Exactly, I think this point is often overlooked, because folks get stuck thinking about the syntax of what they're writing rather than how it works under the hood.
- SOLAR_FIELDS 9y agoIt's nice unless your language has a limiting call stack. JVM languages are notorious for this. You can increase the size of course, if you have the right amount of machinery. Else it's time to explore tail call recursion and other "anti-unrolling" strategies.
- writeslowly 9y agoI think this would be a better lead in than jumping straight to explaining where recursion is useful. Personally, I found it much easier to understand recursion once I had spent enough time experimenting with recursive functions to understand how to convert any algorithm between loop structures and recursive functions. Trying to understand why I'd want to use one over the other followed from that.
- TheOtherHobbes 9y agoThe problem is most introductions to recursion teach the syntax and implementation, not the conceptual structure. The syntax is (usually) "a function calls itself, and there's a stack which can cause problems, except in some languages, probably." The conceptual structure is "Solve a complicated problem by finding a single algo that successfully attacks the problem repeatedly, making the unsolved/unprocessed part smaller and smaller. Repeat until there is no unsolved/unprocessed part left." Then illustrate with examples like Hanoi that demonstrate how simple logic applied over and over solves a complex puzzle. Of course it's easy to introduce recursion with factorials, but factorials (etc) don't really explain why recursion is powerful. They make it look like "Work out this simple math problem (which would be even easier with a for-loop, but whatever) with this one neat trick."
- edmccard 9y ago>Because that's how you transform a recursive call into an iterative one, not nested for loops. I came to understand recursion through nested for-loops, though, but that might just be a historical accident. In the summer of 1988 I had written a Mastermind solver in Microsoft Quickbasic[1] for the specific case of 4 "pegs". At each guess, I used for-loops nested 4 deep to build a structure representing the possible remaining solutions (for all possibilities of the first peg, check all for the second peg, etc.) Then I wanted to extend it to work with variable numbers of pegs; after spending most of that summer trying to figure out a loop-based solution, I discovered that subroutines could call themselves and it hit me that I could have a function that took the possibilities already computed for a peg, and then called itself with those applied to the next peg. So I've always thought of recursion as a way to have arbitrarily deeply nested loops. [1] Believe it or not, it did support recursive functions!
- deleted 9y ago[deleted]
- catmanjan 9y agoQuickbasic was great, fond memories of typing out hundreds of DATA statements for game sprites.
- heavenlyblue 9y agoBut in reality recursion is an arbitrarily nested context that has nothing to do with loops per se (and that's why sometimes it requires the stack and sometimes it does not).
- yen223 9y agoThis neatly explains why recursive depth-first searches are far easier to implement than recursive breadth-first searches. With BFS you'll need to explicitly pass in a queue to track unvisited nodes, whereas with DFS you already get a stack for free!
- neukoelln 9y agoAnd you will also get a stack overflow for free.
- greghendershott 9y agoIn some languages the "stack" may grow until all memory is exhausted. (Some of those languages also guarantee tail call elimination.)