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."

Here is 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 easier problems, then:
   • Solve the easier problems.

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 may need to be further broken up.