Recursion and Choosing the Right Data Structure

This unit closes with two threads that tie everything together: recursion, the technique that expresses many data-structure algorithms most naturally, and the wider skill of selecting the right structure for a given problem. Both are favorite targets of exam questions because they test understanding rather than memorization.

What recursion is

Recursion is a problem-solving technique in which a function calls itself to solve a smaller version of the same problem. Every correct recursive definition has two essential parts:

• A base case — a condition simple enough to answer directly without further recursion. It stops the process.
• A recursive case — the step that reduces the problem toward the base case and calls the function again on the smaller problem.

Without a base case, or if the recur