Recursion Primer
A function that calls itself on a smaller problem until it reaches a base case. You need this for trees (Ch 6) and merge/quick sort (Ch 8).
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
Russian matryoshka dolls: to find the smallest doll you open a doll, and inside is… a smaller doll, which you open the same way. You stop when a doll doesn’t open. That last doll is the base case.
Two required parts
- Base case: a small input you can answer directly, with no further calls (
n <= 1→ return 1). - Recursive case: solve the problem using the answer to a smaller version of itself (
n * factorial(n - 1)). Each call must move toward the base case.
The call stack
Every call gets its own stack frame (its own copy of n, its own return address). When factorial(4) calls factorial(3), the first call pauses and waits. Frames pile up until the base case returns, then they unwind one by one, each finishing its multiplication.
That’s why recursion uses O(depth) memory, and why a missing base case ends in a stack overflow.
When to use it
Recursion shines when a problem naturally contains smaller copies of itself: trees (a subtree is a tree), divide and conquer sorts (merge and quick sort), and searching by halves.
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
Watch frames pile up until the base case, then unwind with return values.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
using namespace std;
int factorial(int n) {
if (n <= 1) return 1; // base case: stops the recursion
return n * factorial(n - 1); // recursive case: smaller problem
}
int bs(const int a[], int low, int high, int key) {
if (low > high) return -1; // base case 1: empty range
int mid = (low + high) / 2;
if (a[mid] == key) return mid; // base case 2: found
if (a[mid] < key) return bs(a, mid + 1, high, key);
return bs(a, low, mid - 1, key);
}
void countDown(int n) {
if (n == 0) { cout << "liftoff!\n"; return; }
cout << n << " ";
countDown(n - 1);
}
int main() {
cout << "5! = " << factorial(5) << "\n";
int a[] = {2, 5, 9, 14, 20, 27, 33, 41};
cout << "bs(27) -> " << bs(a, 0, 7, 27) << "\n";
cout << "bs(4) -> " << bs(a, 0, 7, 4) << "\n";
countDown(3);
}5! = 120 bs(27) -> 5 bs(4) -> -1 3 2 1 liftoff!
05Complexity
| factorial(n): time | O(n): n calls, O(1) work each |
|---|---|
| factorial(n): space | O(n) stack frames |
| recursive binary search: time | O(log n) |
| recursive binary search: space | O(log n) stack frames (iterative version: O(1)) |
Every recursive call uses a stack frame. Too deep (or no base case) means a stack overflow and a crash.
06Watch
Recursion (CS50 Shorts)
Why this one: CS50's short is the friendliest explanation of base case, recursive case and the call stack.
5 Simple Steps for Solving Any Recursive Problem
Why this one: A 5-step method for writing recursive functions. It pays off in Ch 6 and Ch 8.
Original class slides (Python, by the course's lecture authors):Sorting Basics
07Exam lens
Likely questions
- What is recursion? What are the two required parts of a recursive function?
- Trace
factorial(4)showing the call stack. - Write a recursive binary search function.
- What happens if a recursive function has no base case?
Common mistakes
- No base case, or a base case that is never reached (e.g.
factorial(n + 1)). - Forgetting to
returnthe recursive call's result (bs(...)instead ofreturn bs(...)). - Thinking recursion is always slower or always better. It trades stack memory for simpler code.
08Quick check
09Practice
🟢 Trace by hand
Trace power(2, 4) where power(b, e) returns 1 if e == 0, else b * power(b, e - 1). Show the calls going down and the values coming back up.
Show answer
Down: power(2,4) → power(2,3) → power(2,2) → power(2,1) → power(2,0)
Up: power(2,0) = 1 → power(2,1) = 2 → power(2,2) = 4 → power(2,3) = 8 → power(2,4) = 16
🟡 Implement it
Write recursive sumArray(a, n), reverseString(s, l, r) and fib(n). Which one is slow for n = 40 and why?
Hint
fib(n) = fib(n-1) + fib(n-2) recomputes the same values exponentially many times → O(2ⁿ).
Solution
int sumArray(const int a[], int n) { return n == 0 ? 0 : a[n - 1] + sumArray(a, n - 1); }
void reverseString(string& s, int l, int r) { if (l >= r) return; swap(s[l], s[r]); reverseString(s, l + 1, r - 1); }
long long fib(int n) { return n < 2 ? n : fib(n - 1) + fib(n - 2); } // exponential!🔴 Solve problems
Hint
Write it recursively first, then notice the repeated work.
Hint
Base cases: n == 1 → true; n odd or n ≤ 0 → false. Recursive case: isPowerOfTwo(n / 2).
Hint
Swap the ends, recurse on the inside. Base case —
l >= r.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.