Recursion Basics
Quick reference
| factorial(n) | O(n) |
| naive fib(n) | O(2ⁿ) |
| sumArray(arr) | O(n) |
| pow(x, n) — fast power | O(log n) |
Recursion asks a smaller copy of yourself to solve a smaller version of the problem. Then you use that answer to build your answer. To compute factorial(5), you do not need to know how to multiply five numbers together. You need to know 5 × factorial(4). You trust that another copy of you computes factorial(4). That copy trusts another copy for factorial(3). The problem becomes smaller until it reaches a version so small that it can answer immediately with no more questions. This is the base case.
The call stack is the mechanism that makes this work. The call stack is a stack of IOUs. A call to factorial(5) does not get an answer yet. It pushes an IOU that says "I owe you 5 × [the result of factorial(4)]" and waits. factorial(4) pushes its own IOU and waits for factorial(3). This continues until the computer reaches factorial(0). factorial(0) pays immediately: the result is 1, with no wait. Then each call below pays back up the stack in order. factorial(1) gets its answer and returns 1. factorial(2) gets that and returns 2. This continues until factorial(5) finally has its answer.
The word "stack" is not a metaphor. The call stack is a real stack. It is last-in-first-out, the exact structure that Phase 3 covers. The function that was called most recently (and is least resolved) is always the next function to return. You do not need to know this structure by name to write recursion. But it is the reason that recursion and stacks are the same idea in two different forms.
Shape of a recursive function
function solve(problem):
if problem is very small: // base case: answer directly, no recursive call
return direct answer
smallerAnswer = solve(smaller problem) // trust this call to work
return combine(problem, smallerAnswer) // use it to build the answer of this callfactorial — the textbook shape
function factorial(n):
if n == 0: // base case
return 1
return n * factorial(n - 1) // recursive case: trust factorial(n-1), then multiplynaive Fibonacci — the same shape, but it blows up
function fib(n):
if n <= 1: // base case
return n
return fib(n - 1) + fib(n - 2) // TWO recursive calls, not onesum of an array — recursing on 'the rest'
function sumArray(arr, i = 0):
if i == len(arr): // base case: reached the end, nothing left to add
return 0
return arr[i] + sumArray(arr, i + 1) // this element, plus the sum of all elements after itPow(x, n) — divide-and-conquer, a smarter recursion
function pow(x, n):
if n == 0: // base case
return 1
half = pow(x, n // 2) // solve HALF of the problem, one time
if n % 2 == 0:
return half * half // even exponent: square the half
else:
return half * half * x // odd exponent: one more factor of xTime counts the total number of calls. Space counts the deepest point of the call stack, which is the number of IOUs that wait at the same time. This is easy to forget, because it looks like a simple function call, not a data structure. But each pending call stays in memory until it returns.
| Operation | Time | Space | Why |
|---|---|---|---|
| factorial(n) | O(n) | O(n) | There are n calls before the base case. Each of these n calls stays on the stack (it waits for the next call) until the base case returns. This is O(n) stack frames alive at the same time, even though no array or list was made. |
| naive fib(n) | O(2ⁿ) | O(n) | The total number of calls approximately doubles at each level down, which is O(2ⁿ) calls. But at one moment, only one chain of calls is active (the stack unwinds before the next branch starts). So the deepest point of the stack is still only O(n). |
| sumArray(arr) | O(n) | O(n) | There is one call for each element. All n calls wait on the stack at the same time before the base case returns and they pay back up. |
| pow(x, n) — fast power | O(log n) | O(log n) | n is halved at each call, so it takes log₂(n) calls to reach the base case. This is also the depth of the stack, because each call waits for the next call. |
Missing or wrong base case
A recursive function with no base case (or a base case that it never reaches, for example a count up instead of down) pushes IOUs forever until the stack runs out of memory. This is a stack overflow. It is the same shape of bug as a linked list node whose `next` never reaches NULL: a chain with no terminator, walked until something breaks.
Empty input as the trivial base case
Many recursive functions over collections (sum an array, reverse a string) need "nothing left to process" as a base case: the index equals the length, or the array is []. If you skip this and assume there is always at least one element, you make a common off-by-one error. The function crashes or counts too few on the smallest legal input.
Single-element input as the smallest real case
This is different from the empty case. A single element is often the smallest input where the interesting logic runs one time. Test your recursion against a one-element input. This finds bugs that an empty-input test cannot find, for example an off-by-one error in how the recursive call reduces the problem.
Recomputing the same subproblem exponentially many times
fib(5) calls fib(4) and fib(3). fib(4) calls fib(3) and fib(2). fib(3) is now computed two times, and it becomes worse deeper down. The function has no memory of what it already solved. So identical work repeats many times. This is exactly why naive Fibonacci is O(2ⁿ) instead of O(n). The fix (store answers that you already computed) has a name: memoization. But that is a tool for a later phase. For now, only recognize the symptom: overlapping recursive calls that solve the same input more than one time.
Sign in to mark problems done — progress syncs across devices.