Recursion
Learn recursion — when a function calls itself — including base cases, the call stack, and when to use it.
What you'll learn
- What recursion is and how a function calls itself
- The critical importance of a base case
- How the call stack tracks recursive calls
- Converting between recursion and iteration
- When recursion is elegant and when it is wasteful
Concept
Recursion
Recursion is a technique where a function calls itself to solve a smaller version of the same problem. It is an alternative to loops (iteration) for repeating work. Some problems — traversing trees, exploring file systems, parsing nested structures — have a naturally recursive shape that makes recursion the clearest solution.
The Two Essential Parts
Every recursive function needs two things:
- Base case — a condition where the function returns without calling itself. This stops the recursion. Without it, the function calls itself forever.
- Recursive case — the function calls itself with a smaller or simpler input, moving toward the base case.
function factorial(n) {
if (n <= 1) return 1; // base case: stop here
return n * factorial(n - 1); // recursive case: call with n-1
}
Each call to factorial reduces n by 1, moving closer to the base case. The calls stack up, then unwind: factorial(4) becomes 4 * factorial(3), which becomes 4 * 3 * factorial(2), and so on until factorial(1) returns 1.
The Call Stack
When a function calls itself, each call is placed on the call stack — a data structure that tracks which function is currently running and what to return to. The stack grows with each recursive call and shrinks as each call returns. If the recursion is too deep, the stack overflows, producing a stack overflow error. This is why every recursive function must reach its base case in a finite number of steps.
Recursion vs. Iteration
Any recursive function can be rewritten as a loop, and vice versa. The choice depends on clarity:
- Iteration is usually faster and uses less memory (no call stack growth).
- Recursion is clearer for problems with a naturally recursive structure: tree traversal, divide-and-conquer algorithms, nested data processing.
For example, calculating a factorial is equally clear either way. But traversing a file directory — where each folder can contain more folders — is far more elegant with recursion.
When to Use Recursion
Use recursion when the problem is naturally self-similar: "do something, then do the same thing on a smaller piece." Avoid recursion when a simple loop would do the same job more efficiently. In JavaScript, deep recursion (thousands of calls) can cause stack overflow, so for very deep structures, an iterative approach with an explicit stack may be necessary.
Recursion is a thinking tool as much as a coding technique. Learning it trains you to break problems into smaller subproblems — a skill that applies even when you end up writing iterative code.
Example
// Recursive: calculate factorial
function factorial(n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
console.log(factorial(5)); // 120 (5 * 4 * 3 * 2 * 1)
// Recursive: flatten a nested array
function flatten(arr) {
const result = [];
for (const item of arr) {
if (Array.isArray(item)) {
// Recursive case: item is an array, flatten it
result.push(...flatten(item));
} else {
// Base case: item is not an array, add directly
result.push(item);
}
}
return result;
}
console.log(flatten([1, [2, [3, [4]]], 5])); // [1, 2, 3, 4, 5]
// Recursive: countdown with a clear base case
function countdown(n) {
if (n < 0) return; // base case: stop
console.log(n);
countdown(n - 1); // recursive case
}
countdown(3); // prints 3, 2, 1, 0
factorial shows the classic recursive pattern. flatten demonstrates recursion on nested data — each nested array triggers another recursive call. countdown is the simplest example with a clear base case.
Try it
- JSON Tree Viewer
Nested JSON is rendered using recursion — each nested object or array triggers another level of the render function.
- JSON Formatter
Formatting nested JSON requires recursive descent through the structure. Paste deeply nested data to see it in action.
Common mistakes
The mistake
Forgetting the base case, causing infinite recursion and stack overflow.
The fix
Always write the base case first. Ask: 'what is the simplest input where I know the answer?' Return that answer directly before any recursive call.
The mistake
Making the recursive call with the same input, never moving toward the base case.
The fix
Each recursive call must simplify the input — reduce a number, shorten a list, shrink a string. If the input does not change, the recursion never terminates.
The mistake
Using recursion for simple counting when a loop would be clearer and faster.
The fix
If a for loop can express the solution in 3 lines, use a loop. Reserve recursion for naturally recursive problems like tree traversal or nested data.
Related Resources
Related Cheatsheets
- JavaScript Cheatsheet
Reference for function definitions, the call stack, and ES module syntax.
Practice Recursion
6 exercises
Look up unfamiliar terms
A beginner-friendly glossary explains jargon in plain English — variables, functions, DOM, Promise, and more.
Build real projects
Apply what you learned by building guided projects with starter code and solutions.
Decode error messages
Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.