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!
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.
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.
>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.
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.)
Decomposing a problem into functions is something else.
You'll probably find that if you try to create a precise definition of what people generally mean, you can't. Since that's my belief, I didn't try very hard. Getting too wrapped up in labels is often an impediment to understanding anyhow; what's important is that there are legitimately two distinct ways of thinking about how to code, and we aren't really that well served by insisting that they can't be labeled because they can't be precisely defined. (Well, more ways than that, of course, but we're discussing two today.)
I disagree that we can't strive for precision in technical discourse. Programming languages have precise meaning and are executed precisely by a machine. As an industry we are still working to define what these machine can really do to help along precise definitions can aid in communication complex topics. We could not have loops or recursion if simpler construct like conditions, jumps, gotos, variables and others did not have precise definitions.
It does seem that this, how humans approach problems with these two kinds of problem decomposition, is close to the boundary of natural and machine language. This might rule it out from precise definition, but it seems to be worth a try to me.
If people unconsciously create a more complex cycle, that might even be decomposable into distict smaller cycles, then thats still a perfectly fine recursion.
A program can apply both, recursion and iteration, together to solve a problem. Maybe the problem in the conversation is that it's context is implicit and inconsistent.
A recursive solution can always be written as an iterative one. Recursion is just a treat given by the language. There could be a language where any type of recursion on the language-function level is forbidden, but I doubt it would be terribly successful.
In an explicit representation of the "work graph" you can easily prove a finite number of walks or a cycle (and then break it in some way). Doing that directly for a nontrivial function without using graph theorems is much harder.
Yes it is "easier" syntactically but then also easy to shoot yourself in the foot. Since a function call is a primitive you only get primitive tools to handle problems with it. Exceptions for example tend to unwind the stack which can take a long time. In functional languages you can end up with Bottom state from nowhere or a plain old crash.
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.
>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.
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.
Trying to understand why I'd want to use one over the other followed from that.
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."
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.
You can't always know how much of the implementation stack will already be used by whatever calls your code, after all. It's a weird kind of "shared resource".
(Some of those languages also guarantee tail call elimination.)
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.