Recursion on the Rocks

Here (again) are the 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.

Here are how this applies to the rock-destruction problem:

1. When a piece is small, don't pound it any further.
2. To destroy a large rock, hit it with a hammer. The rock shatters, leaving small and large pieces.
   • Apply this procedure to each of the pieces.