11 Recursion

12 Recursion

Week 5, Session 1. CSS 342.

12.1 Warmup

Climbing Stairs (#70). You can take 1 or 2 steps at a time. How many distinct ways to climb n stairs?

class Solution {
 public:
  int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; ++i) {
      int c = a + b;
      a = b;
      b = c;
    }
    return b;
  }
};

That is the iterative answer. The recursive answer is:

int climbStairs(int n) {
  if (n <= 2) return n;
  return climbStairs(n - 1) + climbStairs(n - 2);
}

Same problem. Different shape. Fibonacci in disguise. We will talk about why one of these is exponential and the other linear later in this chapter.

12.2 Learning objectives

Identify the base case and recursive case in any recursive function.
Trace a recursive call stack by drawing stack frames.
Implement factorial, power, and binary search recursively.
Convert between recursive and iterative implementations for simple problems.
Recognize when recursion is naturally superior to iteration (tree traversal preview).

12.3 The anatomy

Every recursive function has three pieces:

Base case — when to stop. The smallest version of the problem you can answer directly.
Recursive case — how to reduce the problem to a smaller version of itself.
Progress — every recursive call must move strictly toward the base case.

If you forget the base case: infinite recursion, stack overflow. If the recursive case does not shrink the problem: infinite recursion, stack overflow.

int factorial(int n) {
  if (n == 0) return 1;        // base case
  return n * factorial(n - 1); // recursive case (n - 1 is smaller)
}

That is the canonical first recursive function. Read it as: “the factorial of n is n times the factorial of n minus one, and the factorial of zero is one.”

12.4 Trust the recursion

The hardest part of writing recursion is trusting that the recursive call works. When you write factorial(n - 1), you have to believe the function correctly returns (n-1)! even though you have not finished writing it. This is uncomfortable. It is also the only way recursion works.

The trick is to think two levels:

Base case: write the smallest answer directly.
Recursive case: assume the recursive call works on a smaller input. Use its answer to build yours.

That is it. Do not trace through every level in your head. The compiler does that. You write the what; the runtime handles the how.

Students try to trace the entire call stack to “understand” recursion. That is the wrong move. You do not trace a for loop — you reason about the loop invariant. Same with recursion: reason about the recursive contract.

12.5 The box trace

When you do need to trace recursion — for debugging or for an exam question — use the box trace technique:

Draw a box for each call. Label it with the function name and arguments.
Draw an arrow from the calling box to the new box.
When a box returns, write the return value on the arrow.
Cross off the box.

factorial(4)
└─ 4 * factorial(3)
        └─ 3 * factorial(2)
                └─ 2 * factorial(1)
                        └─ 1 * factorial(0)
                                └─ returns 1
                        ← returns 1
                ← returns 2
        ← returns 6
← returns 24

The call stack grows from top to bottom, then unwinds from bottom to top. Every call gets its own stack frame; every return pops one.

12.6 Stack overflow

Each call costs a stack frame. The stack is finite — typically 1 to 8 MB. A function that recurses 100,000 deep will probably crash with stack overflow:

int countdown(int n) {
  if (n == 0) return 0;
  return countdown(n - 1);
}

countdown(1'000'000);   // boom (probably)

The same logic iteratively uses constant stack:

int countdown(int n) {
  while (n > 0) --n;
  return 0;
}

So when is recursion preferred? When the problem has recursive structure: trees, divide-and-conquer, backtracking. Then recursion is clearer than iteration even if both work.

12.7 Power — divide and conquer

// Naive: O(n) calls
double power(double base, int exp) {
  if (exp == 0) return 1;
  return base * power(base, exp - 1);
}

// Smart: O(log n) calls
double powerFast(double base, int exp) {
  if (exp == 0) return 1;
  double half = powerFast(base, exp / 2);
  if (exp % 2 == 0) return half * half;
  return base * half * half;
}

powerFast(2, 10) makes 4 calls instead of 10: power(2,10) → power(2,5) → power(2,2) → power(2,1) → power(2,0). The trick is that 2^10 = (2^5)^2, so once you have 2^5 you square it.

12.8 Fibonacci — the exponential trap

int fib(int n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

fib(6) calls fib(5) and fib(4). fib(5) calls fib(4) and fib(3). The tree branches at every level. Total calls grow as 2^n. fib(40) is slow on a modern CPU. fib(50) will not finish today.

The fix is memoization — remember the answer the first time you compute it:

unordered_map<int, int> memo;

int fib(int n) {
  if (n <= 1) return n;
  if (memo.count(n) == 1) return memo[n];
  memo[n] = fib(n - 1) + fib(n - 2);
  return memo[n];
}

Each fib(k) is now computed exactly once. The recursion still branches, but every subtree past the first is a cache hit. O(n) total. We will formalize this as dynamic programming in Chapter 33.

Memoization is the bridge from recursion to dynamic programming. Once you see it once, you cannot unsee it. The recursive-tree-with-overlap pattern shows up everywhere — and the fix is always the same: remember what you have already computed.

12.9 Recursive binary search

int bsearch(const vector<int>& v, int target, int lo, int hi) {
  if (lo > hi) return -1;
  int mid = lo + (hi - lo) / 2;
  if (v[mid] == target) return mid;
  if (target < v[mid]) return bsearch(v, target, lo, mid - 1);
  return bsearch(v, target, mid + 1, hi);
}

Identical logic to the iterative version. Each call shrinks [lo, hi] by half. After log_2(n) calls, the range is empty and we return -1. Stack depth is O(log n) — perfectly safe.

12.10 Recursion on strings — reverse and palindrome

string reverseStr(const string& s) {
  if (s.size() <= 1) return s;
  return reverseStr(s.substr(1)) + s[0];
}

That works but is inefficient — substr copies. The natural recursive form requires building a string up via prepend. For a more efficient version, use indices:

void reverseInPlace(string& s, int lo, int hi) {
  if (lo >= hi) return;
  swap(s[lo], s[hi]);
  reverseInPlace(s, lo + 1, hi - 1);
}

And the recursive palindrome check:

bool isPalindrome(const string& s, int lo, int hi) {
  if (lo >= hi) return true;
  if (s[lo] != s[hi]) return false;
  return isPalindrome(s, lo + 1, hi - 1);
}

Same shape: shrink the indices inward until they cross. The “two ends moving inward” pattern, now in recursive clothing.

12.11 Try it

Write sumDigits(int n) recursively. sumDigits(1234) should return 10.

int sumDigits(int n) {
  if (n < 10) return n;
  return n % 10 + sumDigits(n / 10);
}

Then write a recursive function digitSum(int n) that repeatedly applies sumDigits until the result is a single digit. digitSum(9999) → sumDigits(9999) = 36 → sumDigits(36) = 9. Result: 9.

12.12 Self-check

1. Naive recursive Fibonacci is exponential because:

a. Each call allocates a stack frame.
b. The same subproblems are recomputed exponentially many times.
c. Recursion is always slower than iteration.
d. The compiler cannot optimize recursive calls.

b. fib(n) computes fib(k) for each k from 0 to n-2 multiple times. Memoization fixes it.

2. A recursive function with no base case will:

a. Return 0.
b. Compile but produce a warning.
c. Loop forever inside the function body.
d. Recurse until it exhausts the stack and crashes.

d. Each call allocates a stack frame; without a base case, the recursion never terminates and the stack overflows.

12.13 Challenges

Power of Two (#231) — recursive.
Fibonacci Number (#509) — implement memoized.
Reverse Linked List (#206) — recursive version.
Sum of Digits of String After Convert (#1945).

12.14 Where this fits

Recursion is the algorithmic lens through which trees and graphs become tractable. Without it, the chapters on linked lists, BSTs, and traversals would be three times as long. The midterm comes next; then we shift to the discrete-math foundations that make complexity analysis rigorous.

You are here	Coming up
Base case + recursive case, box trace, memoization preview	Chapter 10: midterm review