Two Parts to Recursion

Of course you know how to cross a parking lot. You would probably describe the process as "...keep walking until you reach the entrance."

Let us describe the solution in more detail:

1. If you are one step from the mall, take that step and you are done.
2. If you are further than one step from the mall, divide the distance into two parts:
   • a single step, and
   • the remaining distance.
   Now take a step and then cross the remaining distance.

I've described the solution in a recursive style. There are two parts to recursion:

1. If the problem is easy, solve it immediately.
2. If the problem can't be solved immediately, divide it into smaller problems, then:
   • Solve the smaller problems by applying this procedure to each of them.

The over-all strategy is to find some easily applied action that breaks the problem into smaller pieces. Some of the pieces can be dealt with immediately; others need to be further broken up.