>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.

"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.)

A recursion is a cycle in the graph of function calls.

Decomposing a problem into functions is something else.

That's a technically precise definition that has a boolean-precise meaning, but it doesn't correspond terribly well to what people generally "mean" by the term. Eventually programs people think of as "iterative" will end up with cycles in the call graph simply due to sheer size, rather than the use of any recursive techniques.

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 want to agree that languages are squishy and hard to define things. Some things are well known, but undefinable. I have yet to read a satisfactory definition of "cookie", I mean the little (except when they are big) baked good (except when they aren't baked) that are generally round (except when they aren't) and not the things web browsers store. Most definitions leave out one or more things on common grocery store shelves.

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.

I think iteration and recursion can be defined perfectly well.

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.

Indeed. That is a concise definition of recursion. But why have a cycle in a call stack (implicitly linearizing a graph) when you can replace it with a cycle in your data structure without spooky action at a distance controlled by a compiler?

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.