4.6 Summary

By breaking problems down into simpler problems we can develop solutions to complex problems. Many problems can be solved by combining instances of the same problem on simpler inputs. When we define a procedure to solve a problem this way, it needs to have a predicate expression to determine when the base case has been reached, a consequent expression that provides the value for the base case, and an alternate expression that defines the solution to the given input as an expression using a solution to a smaller input.

Our general recursive problem solving strategy is:

  1. Be optimistic! Assume you can solve it.

  2. Think of the simplest version of the problem, something you can already solve. This is the base case.

  3. Consider how you would solve a big version of the problem by using the result for a slightly smaller version of the problem. This is the recursive case.

  4. Combine the base case and the recursive case to solve the problem.

I’d rather be an optimist and a fool than a pessimist and right.
Albert Einstein

Einstein, Albert For problems involving numbers, the base case is often when the input value is zero. The problem size is usually reduced is by subtracting 1 from one of the inputs.

In the next chapter, we introduce more complex data structures. For problems involving complex data, the same strategy will work but with different base cases and ways to shrink the problem size.