Recursion is a programming technique where a function calls itself to solve a smaller instance of the same problem. It’s a natural fit for tasks that have a self-similar structure, like navigating folders, traversing a tree/DOM, or breaking problems into smaller subproblems (divide and conquer).
If recursion feels abstract, this guide will make it practical. You’ll see how to write recursive functions safely, where they shine, when to avoid them, and how to make them fast.
What You’ll Learn
- What recursion is and how it works in JavaScript
- The two essential parts of every recursive function (base case & recursive case)
- Common examples: factorial, Fibonacci, nested data traversal, and tree/DOM traversal
- Performance and memory implications (and how to avoid stack overflows)
- Techniques like memoization and converting recursion to iteration
- Best practices and simple debugging tips
What Is Recursion?
In programming, recursion refers to a function calling itself with smaller inputs until it encounters a base case, which serves as the stopping point.
Two parts of any recursive function:
- Base case: Stops the recursion.
- Recursive case: Reduces the problem and calls the function again. If either part is missing or incorrect, you’ll likely hit infinite recursion or a stack overflow.
Anatomy of a Recursive Function (Template)
function solve(problem) {
if (isSimple(problem)) { // 1) Base case
return simpleAnswer(problem);
}
const smaller = reduce(problem); // 2) Recursive case
return combine(solve(smaller));
}
Keep this mental template handy; you’ll reuse it constantly.
Example 1: Factorial (Intro to Recursion)
n! = n × (n − 1) × ... × 1; and by definition 0! = 1
function factorial(n) {
if (n < 0) throw new Error("n must be >= 0");
if (n === 0) return 1; // base case
return n * factorial(n - 1); // recursive case
}
console.log(factorial(5)); // 120
Pitfall to avoid: Forgetting the base case or letting n go negative.
Example 2: Fibonacci (Naive vs Memoized)
The nth Fibonacci number is defined as:
- F(0) = 0, F(1) = 1
- F(n) = F(n − 1) + F(n − 2)
Naive (simple but slow)
function fib(n) {
if (n < 0) throw new Error("n must be >= 0");
if (n <= 1) return n; // base cases
return fib(n - 1) + fib(n - 2); // overlapping subproblems!
}
Memoized(fast and still recursive)
Cache results to avoid recomputing:
const fibMemo = (function () {
const memo = new Map([[0, 0], [1, 1]]);
return function f(n) {
if (n < 0) throw new Error("n must be >= 0");
if (memo.has(n)) return memo.get(n);
const value = f(n - 1) + f(n - 2);
memo.set(n, value);
return value;
};
})();
console.log(fibMemo(40)); // fast
Takeaway: If recursion leads to repeated work on the same subproblems, optimize it by adding memoization or converting it to dynamic programming.
Example 3: Sum of a Nested Array (Working with Hierarchical Data)
function sumNested(arr) {
let total = 0;
for (const item of arr) {
if (Array.isArray(item)) total += sumNested(item); // recurse into sub-array
else total += item;
}
return total;
}
console.log(sumNested([1, [2, [3, 4]], 5])); // 15
Recursion works perfectly for problems involving hierarchical or tree-shaped structures.
Example 4: Traversing a Tree (Depth-First Search)
const tree = {
value: "A",
children: [
{ value: "B", children: [{ value: "D", children: [] }] },
{ value: "C", children: [{ value: "E", children: [] }, { value: "F", children: [] }] }
]
};
function dfs(node, visit) {
if (!node) return;
visit(node);
for (const child of node.children) {
dfs(child, visit);
}
}
dfs(tree, (n) => console.log(n.value)); // A B D C E F
This pattern mirrors many real-world tasks, like navigating folders or processing JSON trees.
DOM Traversal (Browser Context)
You can traverse the DOM in the browser using a recursive approach.
function countTextNodes(node) {
if (!node) return 0;
let count = node.nodeType === Node.TEXT_NODE ? 1 : 0;
for (const child of node.childNodes) {
count += countTextNodes(child);
}
return count;
}
// Example: countTextNodes(document.body)
Note: This only runs in environments with the DOM (browsers, some testing tools).
Recursion vs. Iteration (When to Use Which)
Prefer recursion when:
- The data is hierarchical (trees, nested lists, DOM, ASTs).
- The algorithm follows a divide and conquer strategy, as seen in quicksort and mergesort.
- You’re doing backtracking (permutations, combinations, path finding).
Prefer iteration when:
- You’re doing simple loops over flat data.
- Depth could be very large (risk of stack overflow).
- Performance/memory is critical, and recursion adds overhead.
Converting Recursive DFS to Iterative (Using a Stack)
function dfsIterative(root, visit) {
if (!root) return;
const stack = [root];
while (stack.length) {
const node = stack.pop();
visit(node);
if (node.children) {
// push right-to-left so left is processed first
for (let i = node.children.length - 1; i >= 0; i--) {
stack.push(node.children[i]);
}
}
}
}
Performance, Stack Depth, and Tail Calls
- Call stack limits: Deep recursion can cause a RangeError: Maximum call stack size exceeded. Limits vary by environment and input size.
- Tail recursion: ES2015 specified proper tail calls, but most JavaScript engines do not optimize tail recursion in practice. Don’t rely on it for safety.
- Enhance efficiency in recursion through memoization, depth restriction, or by rewriting it iteratively.
Debugging Recursive Functions
- Log with indentation to visualize the call stack:
function factorialTrace(n, depth = 0) {
const indent = " ".repeat(depth);
console.log(`${indent}factorial(${n})`);
if (n === 0) return 1;
const result = n * factorialTrace(n - 1, depth + 1);
console.log(`${indent}→ ${result}`);
return result;
}
- Test small inputs first, then scale up.
- Use unit testing frameworks, such as Jest or Vitest, to confirm that your base cases are valid.
Best Practices Checklist
- Always specify a clear base case to ensure the recursion stops correctly.
- Each recursive invocation should shrink the problem size so that it eventually reaches the base case.
- Guard against invalid inputs
- Avoid mutating shared/global state inside recursion
- Use memoization for overlapping subproblems
- Prefer recursion for hierarchical data and backtracking
- Switch to iteration if depth is large or performance suffers
- Add tracing logs or unit tests to verify behavior
Conclusion
Recursion in JavaScript is a powerful tool for problems that decompose naturally, especially hierarchical data, divide-and-conquer algorithms, and backtracking. The key is to write a solid base case, ensure each step reduces the problem, and manage performance with techniques like memoization or by switching to an iterative approach when needed.
With the patterns and examples in this guide, factorial, Fibonacci, nested structures, and tree traversal, you now have a clear, practical foundation to apply recursion confidently and safely in real projects.
You can reach out to me via LinkedIn
Top comments (0)