News for hackers. Stuff that matters.
Re:Dijkstra was right – recursion should not be difficult by jerf on Monday August 07, 2017 @02:22PM (#14949861)
"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.

Re:Dijkstra was right – recursion should not be difficult by edmccard on Monday August 07, 2017 @05:05PM (#14951258)
>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!

Re:Dijkstra was right – recursion should not be difficult by catmanjan on Monday August 07, 2017 @09:14PM (#14952692)
Quickbasic was great, fond memories of typing out hundreds of DATA statements for game sprites.
Re:Dijkstra was right – recursion should not be difficult by heavenlyblue on Tuesday August 08, 2017 @08:32AM (#14957093)
But 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).
Re:Dijkstra was right – recursion should not be difficult by unclebucknasty on Monday August 07, 2017 @03:01PM (#14950242)
>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.

Re:Dijkstra was right – recursion should not be difficult by jerf on Monday August 07, 2017 @03:25PM (#14950430)
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.

Re:Dijkstra was right – recursion should not be difficult by unclebucknasty on Monday August 07, 2017 @03:50PM (#14950668)
>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.

Re:Dijkstra was right – recursion should not be difficult by jerf on Monday August 07, 2017 @04:06PM (#14950822)
"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.)

Re:Dijkstra was right – recursion should not be difficult by madez on Monday August 07, 2017 @11:27PM (#14953827)
A recursion is a cycle in the graph of function calls.

Decomposing a problem into functions is something else.

Re:Dijkstra was right – recursion should not be difficult by jerf on Tuesday August 08, 2017 @09:05AM (#14957370)
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.)

Re:Dijkstra was right – recursion should not be difficult by sqeaky on Tuesday August 08, 2017 @11:31AM (#14958858)
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.

Re:Dijkstra was right – recursion should not be difficult by madez on Tuesday August 08, 2017 @09:31AM (#14957609)
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.

Re:Dijkstra was right – recursion should not be difficult by AstralStorm on Tuesday August 08, 2017 @02:48AM (#14955118)
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.

Re:Dijkstra was right – recursion should not be difficult by AstralStorm on Monday August 07, 2017 @03:09PM (#14950303)
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.

Re:Dijkstra was right – recursion should not be difficult by unclebucknasty on Monday August 07, 2017 @03:34PM (#14950523)
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.

Re:Dijkstra was right – recursion should not be difficult by AstralStorm on Monday August 07, 2017 @05:05PM (#14951259)
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.

Re:Dijkstra was right – recursion should not be difficult by imtringued on Tuesday August 08, 2017 @07:23AM (#14956620)
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.
Re:Dijkstra was right – recursion should not be difficult by writeslowly on Monday August 07, 2017 @03:28PM (#14950450)
I 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.

Re:Dijkstra was right – recursion should not be difficult by TheOtherHobbes on Tuesday August 08, 2017 @03:10AM (#14955221)
The 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."

Re:Dijkstra was right – recursion should not be difficult by Terr_ on Monday August 07, 2017 @07:06PM (#14952035)
> 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.

Re:Dijkstra was right – recursion should not be difficult by SOLAR_FIELDS on Monday August 07, 2017 @08:25PM (#14952426)
It'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.
Re:Dijkstra was right – recursion should not be difficult by joshlemer on Monday August 07, 2017 @09:04PM (#14952646)
Some languages on the jvm (namely scala) do have tail call recursion, meaning that in many cases recursion can use constant stack space
Re:Dijkstra was right – recursion should not be difficult by chii on Monday August 07, 2017 @09:14PM (#14952691)
I thought you had to manually mark the method (and/or the recur site) for scala to do tail call optimisations.
Re:Dijkstra was right – recursion should not be difficult by andrioni on Monday August 07, 2017 @09:24PM (#14952743)
It does the optimization by default, the annotation is to ensure it raises a compilation error if it actually fails to optimize.
Re:Dijkstra was right – recursion should not be difficult by lomnakkus on Wednesday August 09, 2017 @07:26AM (#14967492)
Indeed, and it should be noted that it's quite limited in when it can actually apply the optimization, i.e. self-recursion only (I believe).
Re:Dijkstra was right – recursion should not be difficult by Terr_ on Tuesday August 08, 2017 @12:13AM (#14954186)
I think a useful litmus test is to consider the worst-case depth of whatever you're building. I often feel safer writing my own userland stack, even for stuff like DFS in an interview.

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

Re:Dijkstra was right – recursion should not be difficult by chii on Monday August 07, 2017 @09:16PM (#14952701)
Most languages don't limit stack size at the language level, but at the impl. This is true for Java and for C++.
Re:Dijkstra was right – recursion should not be difficult by yen223 on Monday August 07, 2017 @10:06PM (#14953091)
This 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!
Re:Dijkstra was right – recursion should not be difficult by neukoelln on Tuesday August 08, 2017 @02:16AM (#14954934)
And you will also get a stack overflow for free.
Re:Dijkstra was right – recursion should not be difficult by greghendershott on Tuesday August 08, 2017 @11:24AM (#14958773)
In some languages the "stack" may grow until all memory is exhausted.

(Some of those languages also guarantee tail call elimination.)