Recursion

Recursion is a technique in which a procedure solves a problem by calling itself on smaller instances. It requires a stopping condition to prevent calls from continuing indefinitely.

Base case: A condition that ends a recursive computation without making another recursive call. It supplies the stopping condition that keeps recursive calls from continuing indefinitely.
Induction: A proof method establishing a statement for natural numbers through a base case and an inductive step. Its proof structure mirrors the base case and recursive step of many recursive definitions.
Tree traversal: A systematic process for visiting the nodes of a tree data structure. A traversal naturally applies the same procedure to each subtree.
Iteration: Repeated execution of a block of instructions, typically controlled by a loop. Loops can replace many recursive procedures while avoiding one call frame per step.
Recursive case: A rule that reduces a problem to one or more smaller instances of the same problem. It expresses the self-calling step that makes the procedure recursive.
Structural induction: A proof method that establishes properties by following how recursively defined structures are constructed. It proves properties of recursive data by handling their constructors and smaller components.
Merge sort: A sorting algorithm that recursively sorts two halves of a list and merges them. It demonstrates recursion with independent subproblems and a combining step.
Dynamic programming: An optimization method that stores solutions to overlapping subproblems for reuse. Memoization can prevent recursive solutions from recomputing the same subproblems.
Call stack: A runtime structure that tracks active function calls and their local state. Each unfinished recursive call remains on the stack until deeper calls return.
Divide-and-conquer algorithm: An algorithmic strategy that divides a problem into smaller subproblems, solves them, and combines their results. It commonly implements its repeated subdivision through recursive calls.

Linked from 19 pages