Simplify and Delegate

What is recursion?

Recursion is a particularly powerful kind of reduction, which can be described loosely as follows:

• If the given instance of the problem can be solved directly, we solve it directly.
• Otherwise, we reduce it to one or more simpler instances of the same problem.

How recursion works

If the self-reference is confusing, it may be helpful to imagine that someone else is going to solve the simpler problems, just as we would assume for other types of reductions. We like to call that someone else the “Recursion Fairy.” Our only task is to simplify the original problem or to solve it directly when simplification is either unnecessary or impossible; the Recursion Fairy will solve all the simpler subproblems for us, using methods that are not our concern. Mathematically sophisticated readers might recognize the Recursion Fairy by its more formal name: the induction hypothesis.

There is one mild technical condition that must be satisfied in order for any recursive method to work correctly. There must be no infinite sequence of reductions to simpler and simpler instances. Eventually, the recursive reductions must lead to an elementary base case that can be solved by some other method; otherwise, the recursive algorithm will loop forever. The most common way to satisfy this condition is to reduce to one or more smaller instances of the same problem. For example, if the original input is a skreeble with $n$ glurps, the input to each recursive call should be a skreeble with strictly less than $n$ glurps. Of course this is impossible if the skreeble has no glurps at all. We can’t have negative glurps—that would be silly!—so in that case we must grindlebloff the skreeble using some other method.