The first point to make about recursion is that it is an intrinsically procedural concept. That is, recursion is a sequential process, and much of its power lies in the precise nature of that sequentiality.
Let's talk about the old concept of analysis and synthesis, a way of solving problems by breaking them down into little problems, solving the tiny fragment-problems, and then assembling the fragment-parts back into the whole. This is the core of Western rationalism. But exactly what is the nature of the fragmentation process? What is the cleavage strategy? Normally we cleave a problem by whatever means we can, but with computers we have a more precisely articulated cleavage. The most common way of breaking problems up with the computer is to break them up "side-by-side". For example, suppose I want to print a text document. An obvious solution is to break the document up into individual characters, and then print each character. In other words, my solution reads something like this:
- Get the first character in the document.
- Print that character.
- Get the next character in the document.
- Print that character.
- And so on...
Steps 3 and 4 in this process are called a "loop", and they constitute the core of all programs. But notice how the loop breaks the problem up into a sequence that is arranged from start to finish. The intrinsic nature of a loop is to break a problem up into a sequence with a beginning and an end.
Recursion is the same thing, but it breaks the problem up into an "outside-to-inside" sequence rather than a "beginning-to-end" sequence. The way to understand recursion is to think of it as a way of solving a problem by breaking it down into smaller parts, but they're organized "outside-to-inside" rather than "beginning-to-end".
Let's jump to a quick example. Suppose that you wish to chop various vegetables (problems) up into small parts, but your knife (wit) is rather blunt. You would want to think hard about your cutting strategy. If you had a carrot, you would certainly want to chop it up top-to-bottom (beginning-to-end). You'd do much the same thing with potatoes, celery, or peaches. But how would you tackle an onion? Sure, you could try to cut it up side to side or top to bottom, but with a blunt knife, it would shear up messily. The natural way to cut it up is by layer, outside-to-inside.
Now suppose that you lived in a world without onions. You would think that there's only one way to chop vegetables: top-to-bottom. It would be the natural, obvious, and only way to do the job. So when your genetic scientists labor hard and create -- abracadabra! -- an onion, you'd be flummoxed. Indeed, you'd probably tell the genetic hackers to try again, as they had obviously created an unchoppable vegetable. If only you could learn to think about the problem from an outside-to-inside perspective!
The textbook application for recursion is the maze-traversing algorithm. Suppose that you want to write a program that will move through a maze and find its way out. A recursive solution is the most efficient way to solve the problem. The outside-to-inside nature of recursion is mirrored in its outside-to-inside examination of the maze; it goes deeper and deeper into the maze to find its solution.
As it happens, onions are rare in the real world of computing. I use recursion rarely in my programs. But I often wonder if this is only a consequence of the way I see the world. Perhaps I have chopped so many carrots that I just can't recognize an onion when I see it.