Algorithms from zero
What is recursion?
Imagine finding your way out of a maze. One strategy: at each junction, try one path, and if that path hits a dead end, go back and try another. You apply the same strategy (explore, backtrack, retry) over and over. That is the essence of recursion—a function that solves a problem by calling itself on a smaller version of the same problem, trusting it will work on the smaller version just as it works on the whole.
After this lesson you understand what recursion is: how a function can call itself, what a base case and recursive case are and why both are mandatory, how the recursive leap of faith works (trust the recursive call will do the right thing for the smaller input), and how recursion shines when a problem naturally breaks into smaller copies of itself.
What is recursion?
Recursion is when a function calls itself to solve a smaller version of the same problem. Instead of solving the problem all at once, you break it into two parts:
- Base case: A version of the problem so small you can answer it directly, with no recursion.
- Recursive case: A version of the problem where you call the function on a smaller input, then use that answer to build the answer for your current input.
Both parts are mandatory. Without a base case, the function calls itself forever. Without a shrinking recursive case, you never reach the base case—you loop forever in a different way.
The two mandatory parts
Let us look at a concrete example: computing the factorial of a number.
Factorial is defined as: 5! = 5 × 4 × 3 × 2 × 1 = 120. More generally, n! = n × (n - 1)!.
1
function factorial(n) {
2
// Base case: stop here
3
if (n <= 1) {
4
return 1;
5
}
6
// Recursive case: shrink and call yourself
7
return n * factorial(n - 1);
8
}
- L2 Base case: the smallest input we handle directly. No recursion.
- L5 Recursive case: call factorial on a smaller input, then use the result.
Why does this work? When you call factorial(4), it says: “I need 4 × factorial(3).” You trust that factorial(3) will return 6 (the correct answer for 3!). Then you multiply 4 × 6 = 24. This trust—that the recursive call will do the right thing for the smaller input—is called the recursive leap of faith.
Why the leap of faith works
The key insight: every recursive call passes a smaller input. Eventually, the input shrinks to 1 (or 0), and the base case catches it. At that point, the chain of calls unwinds, each one building its answer from the smaller answer below.
Let us trace factorial(4):
factorial(4) → need 4 × factorial(3)
factorial(3) → need 3 × factorial(2)
factorial(2) → need 2 × factorial(1)
factorial(1) → base case, return 1
factorial(2) → return 2 × 1 = 2
factorial(3) → return 3 × 2 = 6
factorial(4) → return 4 × 6 = 24Recursion vs iteration
Many problems can be solved either way. For example, you can compute factorial with a loop:
result = 1
for i from 2 to 4:
result = result × i
return resultThis is iterative (using a loop, no function calls to itself). It uses less memory (no extra function call stack) and is sometimes faster. But it is less intuitive when the problem is naturally self-similar—like tree traversal, where each node contains smaller subtrees, or merge sort, which splits the array in half recursively.
Recursion shines when the problem structure mirrors recursion: a problem breaks into smaller copies of the same problem. Trees, graphs, permutations, and divide-and-conquer algorithms are natural for recursion.
Let us code recursion in JavaScript and build intuition with two examples.
Example 1: Factorial
function factorial(n) {
// Base case: n <= 1 returns 1
if (n <= 1) {
return 1;
}
// Recursive case: n * factorial(n - 1)
return n * factorial(n - 1);
}
console.log(factorial(4)); // 24
console.log(factorial(5)); // 120Example 2: Sum of integers from 1 to n
Instead of a loop, use recursion:
function sumTo(n) {
// Base case: sum to 1 is 1
if (n <= 1) {
return 1;
}
// Recursive case: n + sum of everything below n
return n + sumTo(n - 1);
}
console.log(sumTo(5)); // 5 + 4 + 3 + 2 + 1 = 15
console.log(sumTo(10)); // 55The pattern is the same: base case for the smallest input, recursive case that shrinks the input and calls itself.
Try both functions:
Let us trace factorial(4) step by step, showing the unwinding of recursive calls.
1
function factorial(n) {
2
if (n <= 1) return 1;
3
return n * factorial(n - 1);
4
}
Time: Each recursive call processes one input value. For factorial(n), there are n calls (from n down to 1), each doing constant work (one multiplication and one comparison). Total: O(n) time.
Space: Each function call takes space on the call stack. The deepest recursion goes from n down to 1, so the stack depth is O(n). This means O(n) space for the stack.
Contrast this with an iterative loop: O(n) time, but O(1) space. Recursion trades space for clarity when the problem is naturally recursive.
Rule of thumb: Use recursion when the problem naturally breaks into smaller copies of itself (trees, graphs, backtracking). The cleaner logic is worth the extra stack space—unless the recursion is very deep (hundreds of thousands of calls), which can overflow the stack.
How many recursive calls happen when you call factorial(5)?
What happens if you forget the base case?
In the sumTo function, what is the base case?
Why does factorial(n) call factorial(n - 1) and not factorial(n) again?
Arrange the steps that happen when you call factorial(3):
- factorial(3) calls factorial(2)
- factorial(2) calls factorial(1)
- factorial(1) hits base case, returns 1
- factorial(2) receives 1, computes 2 * 1 = 2, returns 2
- factorial(3) receives 2, computes 3 * 2 = 6, returns 6
Common mistake
Mistake: No base case. This function has no base case:
function badFactorial(n) {
return n * badFactorial(n - 1);
}It calls itself forever. Even though n shrinks, there is no condition to stop. Eventually the call stack overflows and the program crashes. Every recursive function MUST have a base case.
Common mistake
Mistake: Input does not shrink. This function calls itself on the same input:
function badLoop(n) {
if (n <= 0) return 1;
return badLoop(n); // BUG: n is not shrinking
}Even though there is a base case, the recursive call passes the same n, not n - 1. The base case is never reached (or only if the input is already ≤ 0). The recursive case must shrink the input.
You write a recursive function that counts down from n to 1. What must be true?
Recursion is when a function calls itself to solve a smaller version of the same problem.
Base case: The smallest input the function can handle directly, with no recursion. Example: if (n <= 1) return 1;
Recursive case: The function calls itself on a smaller input, then uses the result to build the answer for the current input. Example: return n * factorial(n - 1);
Both are mandatory: No base case → infinite recursion (crash). Input does not shrink → infinite recursion (crash).
The recursive leap of faith: Trust that the recursive call returns the correct answer for the smaller input. This lets you focus on: “Given the answer for n - 1, how do I build the answer for n?”
Recursion vs iteration: Both can solve the same problem. Iteration is more memory-efficient (no extra call stack). Recursion is more intuitive for problems with recursive structure (trees, graphs, divide and conquer).
Why recursion matters: Trees naturally call recursion (each subtree is a smaller tree). Merge sort and quicksort are easier to understand recursively. Backtracking explores all paths by calling itself on each choice. The next lessons teach the call stack, backtracking, and tree traversal—all built on this foundation.