Recursion and Divide-and-Conquer
Writing a function in terms of a smaller version of itself, and the specific strategy — split, solve, combine — behind some of the most important algorithms in this course.
What you'll learn
- Write a correct recursive function with a proper base case
- Explain the divide-and-conquer pattern: divide, conquer, combine
- Trace a recursive call's execution using the call stack model
Prerequisites
Explanation
A recursive function solves a problem by calling itself on a smaller version of the same problem, combined with a base case — the smallest version of the problem, solved directly, with no further recursive call — that guarantees the recursion eventually stops. factorial(n) = n * factorial(n - 1), with base case factorial(0) = 1, is the canonical example: every call either hits the base case or makes progress toward it by calling itself on a strictly smaller n. A recursive function missing a base case, or one whose recursive call doesn't actually get closer to it, recurses forever — in practice, this crashes with a stack overflow, since each pending call consumes a frame on the call stack, and that stack has a finite size.
The call stack model is the key to understanding why recursion works at all: each call to factorial(n) pushes a new stack frame that waits, paused, at the line n * factorial(n - 1), until the recursive call returns a value — factorial(3) pushes a frame, which calls factorial(2), which pushes another frame, and so on down to factorial(0)'s base case, at which point the stack unwinds: each paused frame resumes exactly where it left off, multiplying by its own n, popping off the stack as it returns. This is genuinely the same stack mechanism the tree-traversal lessons already relied on — a recursive traversal is simply a recursive function whose "smaller problem" happens to be "one of my children's subtrees" instead of "n - 1."
Divide-and-conquer is a specific, powerful recursive strategy with three named steps: divide the problem into smaller subproblems of the same kind, conquer each subproblem recursively (down to a base case simple enough to solve directly), then combine the subproblems' results into the answer for the original problem. Merge sort (next lesson) is the textbook example: divide the array in half, recursively sort each half, then combine by merging the two sorted halves back together — and it's precisely this repeated halving that gives divide-and-conquer algorithms their characteristic O(n log n) complexity, the same halving-and-recombining shape you'll see repeat across several of the algorithms still ahead in this course.
Example
A traced recursive call, with console.log calls showing exactly when each frame is pushed and resumed.
function factorial(n, depth = 0) {
const indent = " ".repeat(depth);
console.log(indent + "call factorial(" + n + ")");
if (n === 0) {
console.log(indent + "base case: return 1");
return 1;
}
const result = n * factorial(n - 1, depth + 1);
console.log(indent + "factorial(" + n + ") returns " + result);
return result;
}
console.log("Final result:", factorial(4));
// Watch the console output: calls go all the way down to the base case
// BEFORE any multiplication happens -- the stack unwinds from the bottom up.Try it yourself
Change factorial(4) to factorial(6) and observe how much deeper the call stack grows before it starts unwinding.
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Guided exercise
Guided exercise
Write fibonacci(n) recursively (fibonacci(0) = 0, fibonacci(1) = 1, fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) for n >= 2). This is intentionally the simple, unoptimized version -- correctness first, not efficiency.
Checks: handles the first base case (n=0) · handles the second base case (n=1) · computes a larger value correctly via recursion
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Independent exercise
Independent exercise
Write sumDigits(n) recursively (n is a non-negative integer) that returns the sum of its decimal digits (e.g. sumDigits(123) = 6). Base case: a single-digit number (n < 10) sums to itself. Recursive case: the last digit (n % 10) plus the sum of the remaining digits (Math.floor(n / 10)).
Checks: sums the digits of a multi-digit number · handles 0 correctly · a single digit is its own sum (base case) · handles a larger multi-digit number
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Common mistakes
- Writing a recursive call that doesn't actually shrink toward the base case (e.g. calling factorial(n) instead of factorial(n - 1) by mistake) -- this recurses forever and crashes with a stack overflow.
- Forgetting a base case entirely, or writing one that's unreachable for some valid input (e.g. only handling n === 0 for a function that might be called with a negative number).
- Assuming recursion is always the most efficient choice -- naive recursive Fibonacci is exponential time due to massive redundant recomputation; recursion's clarity and efficiency are separate concerns, and sometimes an iterative or memoized approach is meaningfully better.
Knowledge check
Takeaway
A correct recursive function needs a base case that's actually reachable from every valid input, and each recursive call must make genuine progress toward it; divide-and-conquer is the specific, powerful pattern of splitting a problem, solving the pieces recursively, and combining their results.
Summary
Recursion solves a problem via a smaller instance of itself plus a base case, using the call stack to pause and resume each pending call. Divide-and-conquer divides a problem into same-kind subproblems, conquers them recursively, and combines the results — the pattern behind merge sort and several algorithms later in this course.
References
Your notes
Notes save automatically.
Finished this lesson?
Mark it complete to track your progress and schedule a future review.
AI tutor
The optional AI tutor isn't enabled in this deployment. All lessons, exercises, quizzes, and search work fully without it.