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 is asking a smaller version of yourself to solve a smaller version of the problem, then using that answer to build yours. To compute factorial(5), you don't need to know how to multiply five numbers together — you just need to know 5 × factorial(4), and trust that some other copy of you will figure out factorial(4). That copy trusts another copy for factorial(3). This keeps shrinking until it hits a version so small it can answer immediately without asking anyone else — the base case.
The call stack — the mechanism that makes this work — is a stack of IOUs. Calling factorial(5) doesn't get an answer yet; it pushes an IOU that says "I owe you 5 × [whatever factorial(4) turns out to be]" and waits. factorial(4) pushes its own IOU and waits on factorial(3). This keeps going until factorial(0) is reached, which pays out immediately: 1, no waiting. Then everyone below it pays back up the stack in order — factorial(1) collects its answer and returns 1, factorial(2) collects that and returns 2, and so on until factorial(5) finally has its answer.
That word "stack" isn't a metaphor — the call stack genuinely is a stack, last-in-first-out, the exact structure Phase 3 covers explicitly. The most recently called (and least resolved) function is always the one that returns next. You don't need to know that structure by name to write recursion, but it's why recursion and stacks are the same idea wearing two different hats.
Shape of a recursive function
function solve(problem):
if problem is trivially 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 this call's answerfactorial — 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: walked off the end, nothing left to add
return 0
return arr[i] + sumArray(arr, i + 1) // this element, plus the sum of everything 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 the problem, once
if n % 2 == 0:
return half * half // even exponent: square the half
else:
return half * half * x // odd exponent: one extra factor of xTime counts total calls made. Space counts the deepest the call stack ever gets — the number of IOUs waiting at once — which is easy to forget since it looks like "just a function call," not a data structure, but every pending call sits in memory until it returns.
| Operation | Time | Space | Why |
|---|---|---|---|
| factorial(n) | O(n) | O(n) | n calls deep before the base case, and every one of those n calls stays on the stack (waiting on the next) until the base case returns — that's O(n) stack frames alive at once, even though no array or list was ever created. |
| naive fib(n) | O(2ⁿ) | O(n) | Total calls roughly double each level down — O(2ⁿ) calls overall. But at any single moment, only one chain of calls is active at a time (the stack unwinds before the next branch starts), so the deepest the stack ever gets is still just O(n). |
| sumArray(arr) | O(n) | O(n) | One call per element, and all n calls are waiting on the stack simultaneously before the base case returns and they start paying back up. |
| pow(x, n) — fast power | O(log n) | O(log n) | n is halved every call, so it takes log₂(n) calls to reach the base case — and that's also how deep the stack gets, since each call waits on the next. |
Missing or wrong base case
A recursive function with no base case (or a base case that's never reached — e.g. counting up instead of down) keeps pushing IOUs forever until the stack runs out of memory: a stack overflow. It's the exact 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 — index equals length, or the array is []. Skipping this and assuming there's always at least one element is a common off-by-one source: the function crashes or under-counts on the smallest legal input.
Single-element input as the smallest real case
Distinct from the empty case — a single element is often the smallest input where the 'interesting' logic actually runs once. Testing your recursion against a one-element input catches bugs that an empty-input test can't, like an off-by-one in how the recursive call narrows 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) just got computed twice, and it only gets worse deeper down. The function has no memory of what it already solved, so identical work repeats over and over, which is exactly why naive Fibonacci is O(2ⁿ) instead of O(n). The fix (caching answers you've already computed) has a name — memoization — but that's a tool for a later phase; for now, just recognize the symptom: overlapping recursive calls solving the same input more than once.
Sign in to mark problems done — progress syncs across devices.