Recursion
A technique where a function solves a problem by calling itself on smaller instances.
Definition
Recursion solves a problem by breaking it into smaller instances of the same problem, with a base case that stops the process. Each recursive call works on a simpler input until the base case is reached.
Deep recursion risks exhausting the call stack, so languages that lack tail-call optimization may require an explicit stack or an iterative rewrite for large inputs. Recognizing when recursion is elegant versus when iteration is safer is a practical judgment.
Every recursive algorithm has an equivalent iterative form using an explicit stack, and the choice between them balances clarity against control over memory. Recursion shines for naturally recursive structures, trees, nested data, divide-and-conquer, where it mirrors the problem's shape. Iteration is safer where inputs are large enough to overflow the call stack. Mastering the translation between the two is a mark of fluency in algorithm design.
Anatomy
- Base case: the simplest input, solved directly.
- Recursive case: reduce the problem and call again.
- Progress toward the base case guarantees termination.
Trade-offs
Recursion often mirrors a problem's natural structure, making code clear, as in tree traversal or divide-and-conquer. The costs are call-stack memory and potential recomputation, which memoization or an iterative rewrite can address.
Why it matters
Recursion is fundamental to many algorithms and to how compilers and interpreters are structured. Understanding it clarifies trees, dynamic programming, and the mathematics of induction.
Fusion connection
Recursive mesh-refinement schemes subdivide regions of a simulation domain where a plasma field varies sharply, concentrating resolution where it is needed.