Imagine you're in a movie theater and you want to know what row you're sitting in. You can't turn around and count from the front. But you can ask the person in front of you: "What row are you in?" They don't know either, so they ask the person in front of them. Eventually, the first person says "Row 1." That answer travels back: "Row 2," "Row 3," until you get "Row 7."
That's recursion. A function that solves a problem by calling itself with a smaller input, until it reaches a version so simple the answer is obvious. Then the answers propagate back up.
You've already seen the stack structure in the previous module. Recursion uses the call stack - each recursive call pushes a frame onto the stack, and when the base case is reached, the frames pop off one by one.
Every recursive function needs two things:
| Approach | Time | Space | When to use |
|---|---|---|---|
| Iterative | O(n) | O(1) | Simple linear problems |
| Recursive | O(recursions) | O(depth) | Tree/graph traversal, divide & conquer |
| Memoized | O(states) | O(states) | Overlapping subproblems |
// Iterative factorial - O(n) time, O(1) space
int FactorialIter(int n) {
int result = 1;
for (int i = 2; i <= n; i++) result *= i;
return result;
}
// Recursive factorial - O(n) time, O(n) stack space
int FactorialRec(int n) {
if (n <= 1) return 1; // base case
return n * FactorialRec(n - 1); // recursive case
}
// Fibonacci - naive: O(2ⁿ) time, O(n) stack space
int FibNaive(int n) {
if (n <= 1) return n;
return FibNaive(n - 1) + FibNaive(n - 2); // exponential!
}
// Fibonacci - memoized: O(n) time, O(n) space
int FibMemo(int n, Dictionary<int, int> memo = null) {
memo ??= new Dictionary<int, int>();
if (n <= 1) return n;
if (memo.ContainsKey(n)) return memo[n];
return memo[n] = FibMemo(n - 1, memo) + FibMemo(n - 2, memo);
}Backtracking is recursion applied to exploring all possibilities. You make a choice, recurse to explore the consequences, then undo the choice and try the next option.
Think of a maze. At each fork, you pick a direction and walk. If you hit a dead end, you backtrack to the last fork and try a different direction. The "undo" step is the key - without it, your path choices accumulate and you can't explore alternative branches.
The template:
This pattern is used for permutations, subsets, combination sums, N-Queens, and Sudoku solvers.
// Generate all subsets (powerset) - O(2ⁿ)
IList<IList<int>> Subsets(int[] nums) {
var result = new List<IList<int>>();
var current = new List<int>();
Backtrack(0);
return result;
void Backtrack(int start) {
result.Add(new List<int>(current)); // add current subset
for (int i = start; i < nums.Length; i++) {
current.Add(nums[i]); // choose
Backtrack(i + 1); // explore
current.RemoveAt(current.Count - 1); // un-choose
}
}
}
// Generate all permutations - O(n!)
IList<IList<int>> Permute(int[] nums) {
var result = new List<IList<int>>();
var current = new List<int>();
var used = new bool[nums.Length];
Backtrack();
return result;
void Backtrack() {
if (current.Count == nums.Length) {
result.Add(new List<int>(current));
return;
}
for (int i = 0; i < nums.Length; i++) {
if (used[i]) continue;
used[i] = true;
current.Add(nums[i]);
Backtrack();
current.RemoveAt(current.Count - 1);
used[i] = false;
}
}
}A recursive pattern that shows up everywhere in computer science:
It sounds abstract, but you've already seen it: binary search (from the Big O module), merge sort, quick sort, and many tree algorithms all follow this pattern. The key insight is that if you can solve a smaller version of the problem, you can combine those solutions to solve the full problem.
int Sum(int[] arr, int left, int right) {
if (left == right)
return arr[left]; // base case
int mid = left + (right - left) / 2;
int leftSum = Sum(arr, left, mid); // divide
int rightSum = Sum(arr, mid + 1, right); // divide
return leftSum + rightSum; // combine
}
// Sum(arr, 0, arr.Length - 1) to start
// O(n) time, O(log n) stack spaceRecursion works best when:
Iteration is better when:
Decision guide:
| Pattern | Use recursion? |
|---|---|
| Tree traversal | Yes - natural recursive structure |
| Array iteration | No - simple loop is faster |
| Permutations / subsets | Yes - backtracking is naturally recursive |
| Factorial / Fibonacci | Memoized recursion or iteration |
| Divide & conquer | Yes - split, solve, combine |
| Level-order processing | No - queue iteration is simpler |
Warning signs for recursion:
Missing base case (infinite recursion) Without a base case, the recursion never stops and you get a stack overflow. Always write the base case first.
Not returning the recursive result
factorial(n) = n * factorial(n - 1) - if you forget the return, the function returns nothing. Always propagate the result back up.
Naive Fibonacci is O(2ⁿ)
fib(n) = fib(n-1) + fib(n-2) without memoization recomputes the same values exponentially. For n=50, it's trillions of calls. Use memoization (caching) or iteration.
Stack overflow from deep recursion Each call adds a stack frame. Beyond ~1000 frames (Python) or ~10000 (C#/Java/C++), you risk overflow. For linear problems, consider the iterative version.
Forgetting to undo in backtracking If you modify shared state (like a list) during recursion and don't undo it, sibling branches see corrupted state. The "undo" step in backtracking is not optional.
Confusing recursion depth with problem size A recursive function on a balanced binary tree of n elements has O(log n) depth, not O(n). The depth depends on the structure, not the total element count.
Recursion gives you a powerful way to think about problems - especially ones that can be broken into smaller versions of themselves.
Now we'll apply that thinking to Sorting & Searching. Sorting is the ultimate divide-and-conquer success story. Algorithms like Merge Sort and Quick Sort are textbook examples of recursion in action. And searching - especially binary search - is the O(log n) superpower we hinted at way back in the Big O module.
Next up: Sorting & Searching