Recursion and Divide and Conquer: every key term you need (+ practice quiz)
25 flashcard terms for Data Structures & Algorithms Topic 3, written to match the course framework. Study them here, then drill them as interactive flashcards, or test yourself with the 15-question quiz — free, no account needed.
The smallest input a recursive routine answers directly without calling itself. Omitting or mis-stating it is the usual cause of infinite descent and exhausted stack memory.
Recursive case
The branch that reduces the problem to one or more strictly smaller instances and combines their answers. Progress toward the base case is what guarantees termination.
Recursion depth
The maximum number of nested calls alive at once. Merge sort reaches about log n depth while naive list recursion can reach n, which is why the latter overflows on big inputs.
Stack overflow
The runtime failure that occurs when nested calls exceed the allotted stack region. Deep or missing base cases cause it, and converting to iteration or an explicit stack cures it.
Tail recursion
A form where the recursive call is the final action, with nothing left to compute afterwards. It can be rewritten as a loop because the caller's frame is no longer needed.
Tail call optimization
A compiler transformation that reuses the current frame for a call in tail position, turning recursion into a jump and holding stack use constant. Not all language runtimes provide it.
Mutual recursion
Two or more routines that call each other in a cycle, common for parsing grammars where an expression rule calls a term rule which calls the expression rule again.
Divide and conquer
A design paradigm that splits input into subproblems, solves them recursively, and merges the results. Its cost is captured by a recurrence and usually solved with the master theorem.
Combine step
The work done after recursive calls return, such as merging two sorted halves. Its cost is the non-recursive term of the recurrence and often decides the final bound.
Merge sort
Splits the array in half, sorts each half recursively, and merges. Runs in Theta(n log n) on every input, is stable, and needs linear auxiliary space for the merge buffer.
Recursive binary search
Compares the target to the middle key of a sorted range and recurses into one side. Depth is about log n and, being tail recursive, it converts cleanly into a loop.
Quickselect
Finds the kth smallest element by partitioning and recursing into only the side containing k. Expected linear time with a random pivot, quadratic in the worst case.
Median of medians
A deterministic pivot rule that groups elements by fives and recurses on the medians, guaranteeing a constant fraction split and giving worst-case linear selection.
Closest pair of points
A planar problem solved by splitting on x, recursing, then checking a narrow strip around the dividing line where only a constant number of neighbours matter, for O(n log n) total.
Maximum subarray by splitting
Finds the best contiguous sum by taking the best in each half plus the best crossing the midpoint, giving O(n log n) before the linear scanning method improves on it.
Exponentiation by squaring
Computes a raised to n with about log n multiplications by squaring repeatedly and multiplying in a factor for each set bit of the exponent.
Karatsuba multiplication
Multiplies large numbers with three recursive half-size products instead of four, lowering the exponent from two to about log base 2 of 3, roughly n raised to 1 point 585.
Strassen multiplication
Multiplies matrices with seven recursive products of half-size blocks instead of eight, beating the cubic bound at the cost of extra additions and weaker numerical stability.
Backtracking
Systematic recursive search that extends a partial solution and undoes the last choice when it cannot succeed. It underlies the n queens problem, sudoku solvers and graph colouring.
Search tree pruning
Cutting a branch of a recursive search as soon as a bound or constraint proves no completion can win. It leaves worst-case cost unchanged but transforms typical running time.
Memoized recursion
Caching the answer to each distinct subproblem the first time it is computed so repeats are table lookups. It turns exponential naive recursion into polynomial top-down dynamic programming.
Tower of Hanoi
A puzzle whose recursive solution moves n minus one discs aside, moves the largest, then moves the rest back, requiring two raised to n minus one moves in total.
Recursion to iteration conversion
Rewriting a recursive routine as a loop, trivial for tail position and otherwise requiring the programmer to carry the pending state that frames used to hold.
Explicit stack simulation
Replacing runtime frames with a data stack holding the pending work items, giving iterative depth-first traversal that cannot overflow the call stack on deep inputs.
Branching factor
The number of recursive calls made per level. With branching factor two and halving input the tree has about n leaves, while branching two on n minus one grows exponentially.