17.3. Problems and Sub-problems

As you can probably imagine, we generally want to avoid infinite recursion. That’s why make sure our recursive algorithms make progress toward the base case. To do this, we typically want our recursive call to work on a smaller version of the original problem – eventually reaching the base case. A few general definitions:

• Problem: what you’re trying to solve.

• Sub-problem: a smaller version or part of the problem that’s easier to solve.

With respect to recursion:

• Recursive Cases: sub-problems that cannot be solved directly.

• Base Cases: sub-problems that can be solved directly.