Recursion and Recurrences

Recursive algorithms solve a problem by solving smaller versions of it, and their cost is captured by recurrence relations.

What recursion is

A recursive algorithm solves a problem by reducing it to smaller instances of the same problem, plus some combining work. It needs a base case that stops the recursion and a recursive case that shrinks the input. Divide-and-conquer methods like merge sort and binary search are recursive by design.

Recurrence relations

The running time of a recursive algorithm is expressed as a recurrence: the cost T(n) in terms of the cost on smaller inputs. Merge sort splits into two halves and merges in linear time, giving T(n) = 2 T(n/2) + O(n). Solving the recurrence yields the closed-form complexity.

Ways to solve recurrences

• Recursion tree: sum the work across all levels of the call tree
• Substitution: guess a bound and prove it by induction
• Master theorem: a formula for divide-and-conquer recurrences

A worked solution

For T(n) = 2 T(n/2) + O(n): the tree has log n levels, and each level does O(n) total work (the halves sum back to n). Multiplying gives O(n log n). That matches merge sort's known complexity and shows how the recurrence encodes the algorithm's structure.

Recursion depth and space

Each pending recursive call consumes stack memory. Depth n recursion uses O(n) stack space, which can overflow for large inputs. Tail-recursive or iterative reformulations reduce this. The space cost of recursion is as real as the time cost and is easy to overlook.

When recursion is the wrong tool

Naive recursion can repeat work exponentially, as in the plain recursive Fibonacci that recomputes the same subproblems. Dynamic programming and memoization fix this by storing subresults, turning an exponential recursion into a polynomial one. Recognizing overlapping subproblems is the signal to switch.