[rapala]

It's all about precision. To tell someone how to do the dishes seems easy. But give the same instructions to someone who has never done dishes and you quickly see the problem. It goes the other way too. I dare you to try and explain a simple repeating algorithm in prose. No lists or numberings allowed.

Simple recursions work exactly the same as the equivalent iterations. They branch on a condition, execute a step and repeat. How state is handled is the key difference. As Haskell has no concept of a variable, the only way to rebind a name is to recall a function.

I was going to say that a professional in our field who has problems with recursion and the basics of discrete math should take a look in the mirror. But maybe we have managed to raise the abstractions high enough so that one can be productive without knowing the fundamentals of computing. I probably need to broaden my concept of a professional in our field.

[seanmcdirmid]

Even if someone hasn't done the dishes before, contorting the explanation through recursion is not helpful. Recipes and instruction manuals are not recursive, and are rich in direct control flow and avoid indirect (higher order) control flow like the plague. Recursion for human discourse is just not used often, it is a relatively recent concept to us.

There is plenty of program writing to do that don't involve deep knowledge of maths, in fact I would say a vast overwhelming majority of work companies need to get done are not helped by, and possibly even hindered by, an intricate understanding and application of recursion (keep in mind, recursion is actually dangerous in strict languages). Most of us are more like police dectectives using well worn tooling and intuitive problem solving skills to get the job done. Sometimes we might even need the help of a mathemegician, but not most of the time.

[rapala]

Recipes and other manuals are also extremely vague when compared to computer programs. Humans have such vast amounts of context and prior knowledge available to them that pedantic instructions are not needed. The only prior knowledge the computer has is the rest of the program. For this reason I don't like the comparison of natural language and programming languages very much.

I would argue that we use recursion quite a lot. For example, here's how clean a bunch of dishes. If the bunch is no more, your done. Otherwise, take a dish and clean it. Then clean the rest of the dishes like you did with the first one. We often leave out the end condition as it is often clear from the context.

I'm not advocating a deep knowledge of math as I know from experience that it has very few applications in software development. But to me a professional is someone who is not just skilled but knows the history and fundamentals of his trade. He knows not just that for (i = 10; i > 0; i--) terminates but also has an idea why that is so (and what it means that a program terminates).

Why would recursion be any more dangerous than iteration?

[seanmcdirmid]

That is not recursion, but basic procedure call; from wiki:

> Recursion is related to, but not the same as, a reference within the specification of a procedure to the execution of some other procedure. For instance, a recipe might refer to cooking vegetables, which is another procedure that in turn requires heating water, and so forth. However, a recursive procedure is where (at least) one of its steps calls for a new instance of the very same procedure, like a sourdough recipe calling for some dough left over from the last time the same recipe was made. This of course immediately creates the possibility of an endless loop; recursion can only be properly used in a definition if the step in question is skipped in certain cases so that the procedure can complete, like a sourdough recipe that also tells you how to get some starter dough in case you've never made it before. Even if properly defined, a recursive procedure is not easy for humans to perform, as it requires distinguishing the new from the old (partially executed) invocation of the procedure; this requires some administration of how far various simultaneous instances of the procedures have progressed. For this reason recursive definitions are very rare in everyday situations.

http://en.m.wikipedia.org/wiki/Recursion#Informal_definition

Recursion quickly causes a stack overflow when you get it wrong in a strict language (and sometimes even when you get it right!), iteration does not (rather, the CPU just spins and memory is safe). Also, iteration is intrinsically less expressive than recursion, meaning it follows to use it via the principle of least force.

[rapala]

Here's the same in Haskell:

  doDishes []            = done
  doDishes (dish:dishes) = clean dish >> doDishes dishes

Very much a recursion in my opinion.

Recursion can cause stack overflow in lazy language too. But lazy or strict, that's more of an implementation detail although a very visible one. An iteration that appends to a list will run out of memory just the same. I also don't see how a recursion that runs out of stack space is any more dangerouse than an iteration that goes to an infinite loop.

[seanmcdirmid]

That is just a loop in my opinion; it would be easier and more clear to express it as a loop. The power of recursion isn't really necessary, nor is it somehow more enlightened.

Exhausting your call stack in most languages is really bad as far as debugging is concerned: it loses the ability to even form a decent error message (stack overflow), and you are left with poor content for diagnosing the problem. Exhausting the heap or having an infinite loop, in comparison, are vastly easier to debug (the latter being much easier than the former, thrashing the VM system is also a pain in the arse, though less so than exhausting the stack).