Recursion, Recurrence Relations & the Call Stack

Recursion is mathematical induction realized in executable code: an algorithm solves a complex instance by delegating to strictly smaller subproblems of identical structure until reaching a trivial base case. Understanding call stack frame allocation, recurrence trees, and the Master Theorem enables engineers to predict both runtime bounds and stack-overflow boundaries.

By the end of this chapter, you will be able to:

• Trace call stack activation records and memory lifecycles during recursive winding and unwinding phases.
• Formulate recurrence relations for divide-and-conquer and decrease-and-conquer algorithms.
• Solve recurrences using level-by-level summation in the Recursion Tree Method.
• Apply the three cases of the Master Theorem to immediately establish asymptotic bounds for canonical divide-and-conquer algorithms.
• Refactor non-tail recursion into tail recursion with accumulators to leverage compiler Tail-Call Optimization (TCO).

Every mathematically sound recursive algorithm consists of two mandatory components:

1. Base Case (Termination Condition): One or more scenarios evaluated without recursive calls, halting the descent.
2. Recursive Step (Inductive Progression): Decomposes input $n$ into one or more strictly smaller subproblems ($n-1$, $n/2$), guaranteeing progress toward the base case.

ALGORITHM Factorial(n)
    Input: Non-negative integer n
    Output: n!

1.  if n ≤ 1:              // Base Case: Directly solvable
2.      return 1
3.  else:                   // Recursive Step: Strictly smaller subproblem
4.      return n * Factorial(n - 1)

In physical memory, each recursive invocation pushes an Activation Record (Stack Frame) onto the runtime call stack, storing parameters, local variables, and the caller's return instruction address:

• Winding (Descent): Activation records are pushed successively until the base condition evaluates to true ($O(h)$ maximum stack depth).
• Unwinding (Ascent): Completed frames are popped from the stack in LIFO order as deferred operations (e.g., pending multiplications) evaluate and return values to callers.

A Recurrence Relation defines an algorithm's runtime $T(n)$ in terms of its performance on smaller subproblems.

Consider the canonical divide-and-conquer recurrence:

To solve via the Recursion Tree Method, sum the computational work across each level of the tree:

The Master Theorem provides an immediate asymptotic bound for recurrences of the standard form:

Where:

• $a$: Number of recursive subproblems generated per step.
• $b$: Factor by which input size is divided.
• $f(n)$: Work required to partition the problem and merge subproblem results.

Compare $f(n)$ to the Watershed Function $n^{{\log }_{b}a}$ (which represents the asymptotic work done at the leaf level):

1. Merge Sort: $T(n)=2T(n/2)+\Theta (n)$
   $a=2,b=2⟹n^{{\log }_{2}2}=n^1=n$.
   Since $f(n)=\Theta (n)$, Case 2 applies ($k=0$):

   $$T(n)=\Theta (n\log n)$$

2. Binary Search: $T(n)=T(n/2)+\Theta (1)$
   $a=1,b=2⟹n^{{\log }_{2}1}=n^0=1$.
   Since $f(n)=\Theta (1)$, Case 2 applies ($k=0$):

   $$T(n)=\Theta (\log n)$$

3. Strassen's Matrix Multiplication: $T(n)=7T(n/2)+\Theta (n^2)$
   $a=7,b=2⟹n^{{\log }_{2}7}\approx n^{2.807}$.
   Since $f(n)=O(n^{2.807-\epsilon })$ with $\epsilon \approx 0.807$, Case 1 applies:

   $$T(n)=\Theta (n^{{\log }_{2}7})\approx \Theta (n^{2.81})$$

A function is Tail-Recursive if the recursive invocation is the final operation before returning; no pending calculations remain.

Non-Tail Recursive (Pending Multiplication):

ALGORITHM FactorialNonTail(n)
1.  if n ≤ 1: return 1
2.  return n * FactorialNonTail(n - 1)  // Must wait for child return to multiply by n

Tail-Recursive (Accumulator Pattern):

ALGORITHM FactorialTail(n, accumulator ← 1)
1.  if n ≤ 1: return accumulator
2.  return FactorialTail(n - 1, n * accumulator) // Final operation: direct tail call

Under Tail-Call Optimization, a compiler reuses the caller's stack frame instead of pushing a new frame, converting the recursive procedure into an $O(1)$ auxiliary space iterative loop at machine level.

• Memory Overhead Invariant: Every non-tail recursive call consumes an activation record on the call stack, contributing $O(h)$ auxiliary space proportional to maximum tree depth.
• The Watershed Comparison: The Master Theorem compares work at the root ($f(n)$) against total work across all leaves ($n^{{\log }_{b}a}$) to determine the dominant asymptotic term.
• TCO Transformation: Pass intermediate state via accumulator parameters to transform linear recursive procedures into tail-recursive loops.

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Chapter 4: Divide-and-Conquer. MIT Press.
2. Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley.
3. Abelson, H., & Sussman, G. J. (1996). Structure and Interpretation of Computer Programs (2nd ed.). MIT Press.