Recursion: Base Case and Decomposition

Recursion solves a problem by calling the same problem on smaller instances. Every recursive method needs at least one base case that answers without self-calling, and one recursive case that guarantees progress toward the base case.

Example: Length of a list: null -> 0; otherwise 1 + length of the rest.

Without a base case or without reduction, infinite recursion occurs.

$$\mathrm{fact}(n)=n\cdot\mathrm{fact}(n-1),\quad \mathrm{fact}(0)=1$$

Where used

File tree walks, DOM/JSON trees, parsers, divide-and-conquer, backtracking. Anywhere data is recursively structured, recursion is the direct mapping of the structure onto control flow.

Depth

A recursive definition requires a base case and a progress measure. For every recursive call, this measure must become smaller in a well-founded order. Only then does termination follow from the structure of the problem.

The base case is not merely a technical termination. It establishes the smallest significance of the function, from which larger results are built. An incorrect return there distorts all higher levels.

Correctness can often be shown inductively: The base case holds true, and assuming correct smaller results, the recursion step produces the correct larger result.

Difficulty levels

1. Identify the base case and recursive step.
2. Specify a strictly descending termination measure.
3. Link an inductive proof to the implementation.

Pitfalls

An achievable base case is not sufficient if some paths do not reduce the measure. Also, a base case checked too late can already trigger an invalid access.