What is the best way to plan a recursive solution to a problem?

Question

I am learning about recursion. I have solved some other problems using recursion, such as creating a binary tree, Towers of Hanoi, etc. So, I understand what recursion is, but I find myself having difficulty planning and implementing a correct recursive solution.

Are there any general tips out there for planning, thinking about, or implementing recursive solutions to a problem?

Answer 1

Basically, just thinking about two things:

• can the problem be expressed in terms of the same (or similar) problem, but with "easier" parameters?
• is there a clear point where that easier problem becomes trivial?

You'll find that those properties are true for all the classic recursive algorithms like binary search, tree traversal, sort/merge, factorial calculations, greatest common denominator calculation and so forth ^(a).

If those two conditions are satisfied, the problem may be suited to a recursive solution.

I say "may" because even problems which exhibit those properties aren't always a good fit for recursion, such as with:

// Add two unsigned inetegers.
unsigned int add (unsigned int a, unsigned int b) {
    if (a == 0)
        return b;
    return add (a - 1, b + 1);
}

Now while that's a somewhat valid recursive solution (albeit a bit contrived), you'll almost certainly run out of stack space when your initial a is large. In other words, the real world will impinge on the purity of mathematical thought.

^(a) You may wonder why there is a difference between something like add above and GCD or factorial calculations. The answer usually lies in how fast the "search space" (the list of all possible outcomes) is reduced with each recursive call.

For example, traversing a balanced binary tree will eliminate roughly half the remaining search space with each call. GCD calculations perform a modulus operation which reduces the search space reasonably fast as well.

The add function, however, doesn't reduce the search space very quickly at all, which is why it's inappropriate for recursion.

The factorial one also doesn't reduce the search space that quickly since it subtracts one from the argument each recursive call (similar to add).

People still use it however, possibly because you'll run out of storage space for the factorial long before the number of recursive calls makes a difference (a 64-bit unsigned integer will only hold about 20!).

Answer 2

Once identified that the problem can be solved recursively, one of the most important things to do is to identify what's going to be the stop condition of your recursive algorithm. A trivial example is the calculation of factorial: you know that you should stop either when you get to 0 or 1 (whatever you choose) therefore that should be the first thing you check in entering your function before allowing the recursion to continue if you don't want end up with a stack overflow exception:

public static int factorial(int n)
{
    if (n == 1)//I'm done
        return 1;
    return n * factorial(n - 1); //continue with the recursion
}

That's pretty much my recipe for recursion: What's the stop condition? Put it as the first statement after entering your recursive function.

Answer 3

Recursion is all about identifying "self-similarity" within the process of solving a problem. A typical example of recursion, calculating the factorial of a positive integer shows this process very well.

Since factorial, n!, is defined as n * (n-1) * (n-2) ... * 1, you should be able to see that

n! = n * (n-1)!

In other words, The factorial of n is "n times the factorial of (n-1)".

If you can understand that statement, and how it exhibits "self-similar" behavior, then you are well primed to tackle recursion. The critical thing when programming recursion is identifying when to stop, and NOT perform the recursive call. In the case of factorial, you stop when the number you are trying to determine the factorial of is 1. The result is simply defined as 1, so you return that value instead of returning the value of the recursive function call.

So my suggestion when thinking about how to tackle a problem recursively is to try to identify this self-similarity in the problem at hand. If you can easily identify such similarity then the problem probably has an efficient and elegant recursive solution. If such self-similarity is not evident, it is probably better suited to an iterative approach.

Answer 4

Usually, there's a couple of tasks you'll want to approach to devise a recursive algorithm. I'll use the Towers of Hanoi problem as an example, since it fits the bill pretty well.

First and foremost, make sure that you can see the problem itself in terms of a recursive definition. Specifically, you want to identify how the whole problem can be described as operating on a similar, smaller sub-problem plus a fixed amount of work.

For the towers of hanoi problem, its a pretty easy case to make that moving a tower of size N is basically the same as moving towers of N-1 and a single disk. It's not immediately obvious without already knowing the solution, though, which disk should be the N+1; either the top or bottom. We need more information.

The next part, which is really a subset of the above issue, is to think about a terminating condition; You have to know when to stop recursing. If you miss this step in your algorithm, you'll end up in an infinite loop or overrunning your datastructure.

Moving a tower of size 1 is totally the same as moving a single disk; there's no reason to recurse. Stated another way, moving a tower of size zero is the same as doing nothing at all, and you can skip that completely.

Finally; you have to identify the invariants that your problem defines in order to guide the way you actually do the work. It basically boils down to finding the things that your algorithm must do so that the smaller sub-problems really do look like the larger problem, and then only recursing under those conditions.

The specific requirement of the Towers of Hanoi is that no disk is permitted to rest on top of a smaller disk. Stated another way, you are not allowed to place a tower on a disk of smaller size than the bottom disk of that tower. Some more reasoning about the problem will lead us to the conclusion that if we split the tower at some point in the middle, and rearrange the disks below the split into some arbitrary, but valid arrangement, then the tower above the split can go on top of any of those rearranged disks, since every single one must be larger than the disk at the split. A similar case cannot be made for rearranging the disks above the split; nothing at all is permitted on top of the top disk.

In total, that implies that we have to work from the bottom up; dividing the tower at the bottom disk. That also means that the degenerate case, the n=1, is moving the top disk. Thus the recursive algorithm is to recursively move N-1 disks aside, move the nth disk to the destination, and then move the N-1 disks onto the destination.

If that's not enough of a guide, then you might want to ask a more specific question