Zen and the Art of Recursion

Throughout this discussion of recursion, we have discussed recursion is almost mystic terms. In a very real sense the right way to think about recursion is that if it works, then it works. For example, in the function to compute the length of a string: 

int strlen( char *s )
{
   if( *s == '\0' )
      return( 0 ) ;
   else
      return( 1 + strlen( s + 1 )) ;
}

we say that if strlen() works on s+1, then we will compute the right value of the length for string s. In other words, if strlen(s+1) works, then strlen(s) works.

As flip as it sounds to say that if strlen() works, then strlen() works, that's really the best way to think about it. When designing a recursive algorithm or function, you need to assume that the algorithm already works. Then you take a problem, and create a smaller version of the same problem. Once that one is solved recursively (remember you assumed that you already had a solution, so use it), you then ask yourself, how can I take the solution to the simpler version of the problem and construct the solution to the larger version. This is exactly what we did when we developed the recursive solution to the Towers of Hanoi. We assumed that we already knew how to move the rings from one tower to another. So we can move n-1 rings from the source to the spare tower. This uncover the nth ring on the source tower which we then move to the destination tower. Now we can use our magic solution for n-1 rings to move the n-1 from the spare tower to the destination placing them back on top of the nth ring. The result of all this is that we have moved n rings from the source to the destination tower. In other words, if we can move some number of rings, then we can move one more than that number. Since we can move a single ring, we can move any number of rings by a domino effect. This is also the basis of the mathematical proof technique called mathematical induction. In fact, we often prove things about recursive algorithms and functions using induction.

The upshot of all this is that you really need to develop an intuitive sense of what recursion is and does. Don't ask how does it solve the problem? Ask instead how does it take a solution to a smaller problem and then build a solution to a bigger problem from it? It's natural to get hung up on the issue of how it gets the solution to the smaller problem in the first place. But don't let yourself do that. Keep focused on the fact that that will arise naturally if two things are true:

  1. The solution to the base case is correct. e.g. the length of an empty string is 0 and
  2. The transformation from the smaller solution to the larger one is correct.

Recursion is that which is recursive.

You may go on to the next part or return to the index.