LOGIC & PUZZLES / ALGORITHMS
Recursion:
a smaller same problem.
A useful recursive definition is not a loop in a mirror; each call must get closer to a clear stopping point.
THE MAIN IDEA
Define a base case and a smaller case.
Recursion solves a problem by expressing it in terms of smaller versions of itself. A recursive function must have at least one base case whose answer can be returned directly, plus a recursive case that transforms the input so progress toward that base case is guaranteed. Computing a factorial is a familiar mathematical example: zero factorial is one, and the factorial of a positive integer n is n multiplied by the factorial of n minus one. Each call reduces n until it reaches zero. Without the base case, the function calls itself indefinitely until the program fails; without a decreasing measure, some inputs may never reach that base case. A useful proof of correctness follows the same structure: show that the base case is correct, then show that if the smaller case is correct, combining it gives the correct larger answer. Tree-shaped data often fits recursion naturally because each branch can be explored using the same procedure. Directory traversal and expression parsing also have this nested shape. However, ordinary linear repetition may be clearer and more memory-efficient when the problem does not have recursive structure. Each call normally occupies stack space, so recursion depth is limited by the runtime and can overflow for large input. An iterative loop with an explicit stack can reproduce many recursive processes while managing memory deliberately. Another trap is repeated work. A naive recursive Fibonacci function calculates the same smaller Fibonacci values many times, causing exponential growth in computation. Memoization stores solved subproblems, turning repeated requests into lookups. Before optimizing, identify the input sizes and complexity that matter. A recursion tree is a useful diagram: write one node per call and connect it to smaller calls, then count repeated subtrees and depth. In code, test the smallest valid input, the input immediately above the base case, and invalid or unusually deep input. Decide whether the empty list or zero value is a base case or an error; the language cannot decide the intended specification for you. Recursion is a way of describing structure elegantly, not a goal in itself. When it makes a complex task easier to reason about, ensure every branch makes progress. When it obscures control flow, iterative code may be the cleaner solution. Both approaches rely on a clear invariant, a defined stopping condition, and enough evidence that the result matches the original problem.
TRY THIS
Trace three nested calls on paper.
Write a function's input at each call, underline the base case, and draw which results return to which parent. Check that the input changes toward the base case every time. A missing change in one branch exposes the infinite recursion risk.