- If the input is a base case, for which the solution is known,
return the solution.
- Otherwise,
- Do part of the problem, or break it into smaller subproblems.
- Call the problem solver recursively to solve the subproblems.
- Combine the subproblem solutions to form a total solution.

- Do part of the problem, or break it into smaller subproblems.

In writing the recursive program:

- Write a clear specification of the input and output of
the program.
- Assume it works already.
- Write the program to use the input form and produce the output form.