How do you solve a problem by breaking it into smaller versions of the same problem? What if a function could call itself to chip away at a task until it's done?
function countdown(n) {
if (n === 0) {
console.log("Done!")
return
}
console.log(n)
countdown(n - 1) // The function calls itself!
}
countdown(3)
// 3
// 2
// 1
// Done!This is recursion. The countdown function calls itself with a smaller number each time until it reaches zero. It's a powerful technique that lets you solve complex problems by breaking them into simpler, self-similar pieces.
What you'll learn in this guide:
- What recursion is and its two essential parts (base case and recursive case)
- How recursion relates to the call stack
- Classic recursive algorithms: factorial, Fibonacci, sum
- Practical applications: traversing trees, nested objects, linked lists
- Recursion vs iteration: when to use each
- Common mistakes and how to avoid stack overflow
- Optimization techniques: memoization and tail recursion
Prerequisite: This guide assumes you understand JavaScript functions. It also helps to know how the call stack works, though we'll cover that relationship here.
What is Recursion?
Recursion is a programming technique where a function calls itself to solve a problem. Instead of using loops, the function breaks a problem into smaller versions of the same problem until it reaches a case simple enough to solve directly. The ECMAScript specification allows functions to reference themselves within their own body, which is the mechanism that makes recursion possible in JavaScript.
Recursion isn't unique to JavaScript. It's a fundamental computer science concept found in virtually every programming language. The patterns you learn here apply whether you're writing Python, C++, Java, or any other language.
Every recursive function has two essential parts:
┌─────────────────────────────────────────────────────────────────────────┐
│ THE TWO PARTS OF RECURSION │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ function solve(problem) { │
│ │
│ if (problem is simple enough) { ← BASE CASE │
│ return solution directly Stops the recursion │
│ } │
│ │
│ return solve(smaller problem) ← RECURSIVE CASE │
│ } Calls itself with simpler input│
│ │
└─────────────────────────────────────────────────────────────────────────┘-
Base Case: The condition that stops the recursion. Without it, the function would call itself forever.
-
Recursive Case: The part where the function calls itself with a simpler or smaller version of the problem.
Here's a simple example that sums numbers from 1 to n:
function sumTo(n) {
// Base case: when n is 1 or less, return n
if (n <= 1) {
return n
}
// Recursive case: n plus the sum of everything below it
return n + sumTo(n - 1)
}
console.log(sumTo(5)) // 15 (5 + 4 + 3 + 2 + 1)
console.log(sumTo(1)) // 1
console.log(sumTo(0)) // 0The function asks: "What's the sum from 1 to 5?" It answers: "5 plus the sum from 1 to 4." Then it asks the same question with 4, then 3, then 2, until it reaches 1, which it knows is just 1.
The Russian Dolls Analogy
Think of recursion like opening a set of Russian nesting dolls (matryoshka). Each doll contains a smaller version of itself, and you keep opening them until you reach the smallest one that can't be opened.
┌─────────────────────────────────────────────────────────────────────────┐
│ THE RUSSIAN DOLLS ANALOGY │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ Opening the dolls (making recursive calls): │
│ │
│ ╔═══════════════════════════════╗ │
│ ║ ║ │
│ ║ ╔═══════════════════════╗ ║ │
│ ║ ║ ║ ║ │
│ ║ ║ ╔═══════════════╗ ║ ║ │
│ ║ ║ ║ ║ ║ ║ │
│ ║ ║ ║ ╔═══════╗ ║ ║ ║ │
│ ║ ║ ║ ║ ◆ ║ ║ ║ ║ ← Smallest doll (BASE CASE) │
│ ║ ║ ║ ╚═══════╝ ║ ║ ║ Can't open further │
│ ║ ║ ║ ║ ║ ║ │
│ ║ ║ ╚═══════════════╝ ║ ║ │
│ ║ ║ ║ ║ │
│ ║ ╚═══════════════════════╝ ║ │
│ ║ ║ │
│ ╚═══════════════════════════════╝ │
│ │
│ Each doll = a function call │
│ Opening a doll = making a recursive call │
│ Smallest doll = base case (stop recursing) │
│ Closing dolls back up = returning values back up the chain │
│ │
└─────────────────────────────────────────────────────────────────────────┘When you find the smallest doll, you start closing them back up. In recursion, once you hit the base case, the return values bubble back up through each function call until you get your final answer.
How Recursion Works Under the Hood
To understand recursion, you need to understand how the call stack works. Every time a function is called, JavaScript creates an execution context and pushes it onto the call stack. When the function returns, its context is popped off. According to MDN's documentation on call stacks, most browsers have a stack size limit — typically around 10,000–25,000 frames — exceeding it throws a RangeError: Maximum call stack size exceeded.
With recursion, multiple execution contexts for the same function stack up:
┌─────────────────────────────────────────────────────────────────────────┐
│ THE CALL STACK DURING RECURSION │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ sumTo(3) calls sumTo(2) calls sumTo(1) │
│ │
│ STACK GROWING: STACK SHRINKING: │
│ ─────────────── ───────────────── │
│ │
│ ┌───────────────┐ ┌───────────────┐ │
│ │ sumTo(1) │ ← current │ │ (popped) │
│ │ returns 1 │ └───────────────┘ │
│ ├───────────────┤ ┌───────────────┐ │
│ │ sumTo(2) │ │ sumTo(2) │ ← current │
│ │ waiting... │ │ returns 2+1=3│ │
│ ├───────────────┤ ├───────────────┤ │
│ │ sumTo(3) │ │ sumTo(3) │ │
│ │ waiting... │ │ waiting... │ │
│ └───────────────┘ └───────────────┘ │
│ │
│ Each call waits for the one above it to return │
│ │
└─────────────────────────────────────────────────────────────────────────┘Let's trace through sumTo(3) step by step:
sumTo(3) is called
n is 3, not 1, so we need to calculate 3 + sumTo(2). But we can't add yet because we don't know what sumTo(2) returns. This call waits.
sumTo(2) is called
n is 2, not 1, so we need 2 + sumTo(1). This call also waits.
sumTo(1) is called — base case!
n is 1, so we return 1 immediately. No more recursive calls.
sumTo(2) resumes
Now it knows sumTo(1) returned 1, so it calculates 2 + 1 = 3 and returns 3.
sumTo(3) resumes
Now it knows sumTo(2) returned 3, so it calculates 3 + 3 = 6 and returns 6.
function sumTo(n) {
console.log(`Called sumTo(${n})`)
if (n === 1) {
console.log(` Base case! Returning 1`)
return 1
}
const result = n + sumTo(n - 1)
console.log(` sumTo(${n}) returning ${result}`)
return result
}
sumTo(3)
// Called sumTo(3)
// Called sumTo(2)
// Called sumTo(1)
// Base case! Returning 1
// sumTo(2) returning 3
// sumTo(3) returning 6Key insight: Each recursive call creates its own copy of the function's local variables. The n in sumTo(3) is separate from the n in sumTo(2). They don't interfere with each other.
Classic Recursive Patterns
Here are the most common recursive algorithms you'll encounter. Understanding these patterns will help you recognize when recursion is the right tool.
The examples below assume valid, non-negative integer inputs. In production code, you'd want to validate inputs and handle edge cases like negative numbers or non-integers.
Practical Use Cases
Recursion really shines when working with nested or tree-like structures. These data structures are naturally recursive, and recursion is often the most elegant solution.
Traversing Nested Objects
Imagine you need to find all values in a deeply nested object:
const data = {
name: "Company",
departments: {
engineering: {
frontend: { count: 5 },
backend: { count: 8 }
},
sales: { count: 12 }
}
}
function findAllCounts(obj) {
let total = 0
for (const key in obj) {
if (key === "count") {
total += obj[key]
} else if (typeof obj[key] === "object" && obj[key] !== null) {
// Recurse into nested objects
total += findAllCounts(obj[key])
}
}
return total
}
console.log(findAllCounts(data)) // 25Without recursion, you'd need to know exactly how deep the nesting goes. With recursion, it handles any depth automatically.
Flattening Nested Arrays
Turn a deeply nested array into a flat one:
function flatten(arr) {
let result = []
for (const item of arr) {
if (Array.isArray(item)) {
// Recurse into nested arrays
result = result.concat(flatten(item))
} else {
result.push(item)
}
}
return result
}
console.log(flatten([1, [2, [3, 4]], 5]))
// [1, 2, 3, 4, 5]
console.log(flatten([1, [2, [3, [4, [5]]]]]))
// [1, 2, 3, 4, 5]Walking the DOM Tree
Traverse all elements in an HTML document:
function walkDOM(node, callback) {
// Process this node
callback(node)
// Recurse into child nodes
for (const child of node.children) {
walkDOM(child, callback)
}
}
// Example: log all tag names
walkDOM(document.body, (node) => {
console.log(node.tagName)
})This pattern combines recursion with higher-order functions (the callback). It's how browser developer tools display the DOM tree and how libraries traverse HTML structures.
Processing Linked Lists
A linked list is a classic recursive data structure where each node points to the next:
const list = {
value: 1,
next: {
value: 2,
next: {
value: 3,
next: null
}
}
}
// Sum all values in the list
function sumList(node) {
if (node === null) return 0
return node.value + sumList(node.next)
}
console.log(sumList(list)) // 6
// Print list in reverse order
function printReverse(node) {
if (node === null) return
printReverse(node.next) // First, go to the end
console.log(node.value) // Then print on the way back
}
printReverse(list)
// 3
// 2
// 1File System Traversal
A conceptual example of how file explorers work:
// Simulated file structure
const fileSystem = {
name: "root",
type: "folder",
children: [
{ name: "file1.txt", type: "file", size: 100 },
{
name: "docs",
type: "folder",
children: [
{ name: "readme.md", type: "file", size: 50 },
{ name: "notes.txt", type: "file", size: 25 }
]
}
]
}
function getTotalSize(node) {
if (node.type === "file") {
return node.size
}
// Folder: sum sizes of all children
let total = 0
for (const child of node.children) {
total += getTotalSize(child)
}
return total
}
console.log(getTotalSize(fileSystem)) // 175Recursion vs Iteration
Every recursive solution can be rewritten using loops, and vice versa. Here's when to choose each:
| Aspect | Recursion | Iteration (Loops) |
|---|---|---|
| Readability | Often cleaner for tree-like problems | Usually simpler for linear tasks |
| Memory | Uses call stack (one frame per call) | Uses fixed/minimal memory |
| Performance | Function call overhead | Generally faster |
| Stack Risk | Stack overflow possible (~10,000+ calls) | No stack overflow risk |
| Best For | Trees, graphs, nested structures | Simple counting, linear arrays |
// Recursive factorial
function factorial(n) {
if (n <= 1) return 1
return n * factorial(n - 1)
}Pros: Matches the mathematical definition exactly. Easy to read.
Cons: Uses O(n) stack space. Could overflow for large n.
// Iterative factorial
function factorial(n) {
let result = 1
for (let i = 2; i <= n; i++) {
result *= i
}
return result
}Pros: Uses O(1) space. No stack overflow risk. Faster.
Cons: Slightly less intuitive mapping to the math.
When to Use Recursion
- Tree structures: DOM traversal, file systems, org charts
- Divide and conquer algorithms: Merge sort, quick sort, binary search
- Problems with self-similar subproblems: Factorial, Fibonacci, fractals
- When code clarity matters more than performance: Prototyping, readable code
When to Use Iteration
- Simple loops: Counting, summing arrays
- Performance-critical code: Tight loops in hot paths
- Very deep structures: Anything that might exceed ~10,000 levels
- Memory-constrained environments: Each recursive call uses stack space
Rule of thumb: Start with whichever approach feels more natural for the problem. If you run into stack overflow issues or performance problems, consider converting to iteration.
Common Mistakes
Here are the most frequent bugs when writing recursive functions:
Mistake #1: Missing or Incorrect Base Case
Without a base case, the function calls itself forever until the stack overflows:
// ❌ WRONG - No base case!
function countdown(n) {
console.log(n)
countdown(n - 1) // Never stops!
}
countdown(3) // 3, 2, 1, 0, -1, -2... CRASH!
// RangeError: Maximum call stack size exceeded// ✓ CORRECT - Has a base case
function countdown(n) {
if (n < 0) return // Base case: stop at negative
console.log(n)
countdown(n - 1)
}
countdown(3) // 3, 2, 1, 0 (then stops)The error you'll see: RangeError: Maximum call stack size exceeded. This means you've made too many recursive calls without returning. Check your base case!
Mistake #2: Base Case That's Never Reached
Even with a base case, if your logic never reaches it, you'll still crash:
// ❌ WRONG - Base case can never be reached
function countdown(n) {
if (n === 0) return // Only stops at exactly 0
console.log(n)
countdown(n - 2) // Skips over 0 when starting with odd number!
}
countdown(5) // 5, 3, 1, -1, -3... CRASH!// ✓ CORRECT - Base case is reachable
function countdown(n) {
if (n <= 0) return // Stops at 0 or below
console.log(n)
countdown(n - 2)
}
countdown(5) // 5, 3, 1 (then stops)Mistake #3: Forgetting to Return the Recursive Call
If you call the function recursively but don't return its result, you lose the value:
// ❌ WRONG - Missing return
function sum(n) {
if (n === 1) return 1
sum(n - 1) + n // Calculated but not returned!
}
console.log(sum(5)) // undefined// ✓ CORRECT - Returns the result
function sum(n) {
if (n === 1) return 1
return sum(n - 1) + n // Return the calculation
}
console.log(sum(5)) // 15Mistake #4: Modifying Shared State
Be careful about variables outside the function that recursive calls might all modify:
// ❌ PROBLEMATIC - Shared mutable state
let count = 0
function countNodes(node) {
if (node === null) return
count++ // All calls modify the same variable
countNodes(node.left)
countNodes(node.right)
}
// If you call countNodes twice, count keeps increasing!// ✓ BETTER - Return values instead of mutating
function countNodes(node) {
if (node === null) return 0
return 1 + countNodes(node.left) + countNodes(node.right)
}
// Each call is independentMistake #5: Inefficient Overlapping Subproblems
The naive Fibonacci implementation recalculates the same values many times:
// ❌ VERY SLOW - Exponential time complexity
function fib(n) {
if (n <= 1) return n
return fib(n - 1) + fib(n - 2)
}
fib(40) // Takes several seconds!
fib(50) // Takes minutes or crashesThis is fixed with memoization, covered in the next section.
Optimizing Recursive Functions
Memoization
Memoization means caching the results of function calls so you don't recompute the same thing twice. It's especially useful for recursive functions with overlapping subproblems.
// Fibonacci with memoization
function fibonacci(n, memo = {}) {
// Check if we already calculated this
if (n in memo) {
return memo[n]
}
// Base cases
if (n <= 1) return n
// Calculate and cache the result
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
return memo[n]
}
console.log(fibonacci(50)) // 12586269025 (instant!)
console.log(fibonacci(100)) // 354224848179262000000 (still instant!)The naive Fibonacci has O(2^n) time complexity. With memoization, it's O(n). That's the difference between billions of operations and just 100.
Tail Recursion
A tail recursive function is one where the recursive call is the very last thing the function does. There's no computation after the call returns.
// NOT tail recursive - multiplication happens AFTER the recursive call
function factorial(n) {
if (n <= 1) return 1
return n * factorial(n - 1) // Still need to multiply after call returns
}
// Tail recursive version - uses an accumulator
function factorialTail(n, accumulator = 1) {
if (n <= 1) return accumulator
return factorialTail(n - 1, accumulator * n) // Nothing to do after this returns
}Why does this matter? In theory, tail recursive functions can be optimized by the JavaScript engine to reuse the same stack frame, avoiding stack overflow entirely. This is called Tail Call Optimization (TCO).
Reality check: Most JavaScript engines (V8 in Chrome/Node, SpiderMonkey in Firefox) do not implement TCO. Safari's JavaScriptCore is the notable exception — it has supported TCO since 2016. So in practice, tail recursion doesn't prevent stack overflow in most environments. The ECMAScript 2015 specification does define tail call optimization in strict mode, but engine adoption remains limited. Still, it's good to understand the concept, as it's important in functional programming languages like Haskell and Scheme.
Converting to Iteration
If you're hitting stack limits, consider converting your recursion to a loop with an explicit stack:
// Recursive tree traversal
function sumTreeRecursive(node) {
if (node === null) return 0
return node.value + sumTreeRecursive(node.left) + sumTreeRecursive(node.right)
}
// Iterative version using explicit stack
function sumTreeIterative(root) {
if (root === null) return 0
let sum = 0
const stack = [root]
while (stack.length > 0) {
const node = stack.pop()
sum += node.value
if (node.right) stack.push(node.right)
if (node.left) stack.push(node.left)
}
return sum
}The iterative version uses heap memory (the array) instead of stack memory, so it can handle much deeper structures.
Key Takeaways
The key things to remember:
-
Recursion = a function calling itself to solve smaller versions of the same problem
-
Every recursive function needs a base case that stops the recursion without making another call
-
The recursive case breaks the problem into a smaller piece and calls the function again
-
Recursion uses the call stack — each call adds a new frame with its own local variables
-
The base case must be reachable — if it's not, you'll get infinite recursion and a stack overflow
-
Recursion shines for tree-like structures: DOM traversal, nested objects, file systems, linked lists
-
Loops are often better for simple iteration — less overhead, no stack overflow risk
-
Watch for stack overflow on deep recursion (most browsers limit to ~10,000 calls)
-
Memoization fixes inefficient recursion by caching results of repeated subproblems
-
Recursion isn't JavaScript-specific — it's a universal programming technique you'll use in any language
Test Your Knowledge
Frequently Asked Questions
Related Concepts
Call Stack
How JavaScript tracks function execution — the foundation of how recursion works under the hood.
Higher-Order Functions
Functions that take or return other functions. Many recursive patterns combine with higher-order functions.
Content coming soon.Data Structures
Trees, linked lists, and graphs — data structures that are naturally recursive.
Content coming soon.Pure Functions
Functions with no side effects. Recursive functions work best when they're pure.
Content coming soon.Reference
Recursion — MDN Glossary
Official MDN definition with common examples including factorial, Fibonacci, and reduce.
Functions Guide: Recursion — MDN
MDN's guide on recursive functions in JavaScript with DOM traversal examples.
Articles
Recursion and Stack
The definitive JavaScript recursion tutorial. Covers execution context, linked lists, and recursive data structures with interactive examples.
What is Recursion? A Recursive Function Explained
Beginner-friendly introduction with step-by-step breakdowns. Great for understanding the "why" behind recursion.
Recursion Explained (with Examples)
Visual explanation of factorial and Fibonacci with tree diagrams. Includes memoization introduction.
JavaScript Recursive Function
Clear tutorial covering recursive function basics, countdowns, and sum calculations with detailed step-by-step explanations.
