How to Use Recursion in JavaScript: Full Tutorial
Learn how to use recursion in JavaScript with clear examples. Covers base cases, recursive cases, call stack behavior, factorial and Fibonacci, tree traversal, and comparing recursion with loops for real-world problem solving.
Recursion is when a function calls itself to solve a problem by breaking it into smaller, identical sub-problems. Each recursive call works on a simpler version of the original problem until it reaches a base case that stops the recursion. Recursion is a fundamental programming technique used for tree traversal, nested data processing, mathematical computations, and many algorithm implementations.
What is Recursion?
A recursive function has two essential parts:
- Base case: The condition that stops the recursion (prevents infinite calls)
- Recursive case: The function calling itself with a simpler version of the problem
javascriptfunction countDown(n) {
// Base case: stop when n reaches 0
if (n <= 0) {
console.log("Done!");
return;
}
// Current step
console.log(n);
// Recursive case: call itself with a smaller number
countDown(n - 1);
}
countDown(5);
// 5
// 4
// 3
// 2
// 1
// Done!How It Works Step by Step
CodecountDown(5) -> prints 5, calls countDown(4)
countDown(4) -> prints 4, calls countDown(3)
countDown(3) -> prints 3, calls countDown(2)
countDown(2) -> prints 2, calls countDown(1)
countDown(1) -> prints 1, calls countDown(0)
countDown(0) -> prints "Done!", returns
returns
returns
returns
returns
returns
Each call waits for its inner call to finish before it can return. This chain of waiting calls is stacked on the call stack.
The Call Stack and Recursion
Every time a function is called, JavaScript adds a frame to the call stack. With recursion, each recursive call adds another frame:
javascriptfunction sum(n) {
if (n <= 0) return 0; // base case
return n + sum(n - 1); // recursive case
}
console.log(sum(4)); // 10Call stack progression:
CodeStep 1: sum(4) -> 4 + sum(3) [sum(4)]
Step 2: sum(3) -> 3 + sum(2) [sum(4), sum(3)]
Step 3: sum(2) -> 2 + sum(1) [sum(4), sum(3), sum(2)]
Step 4: sum(1) -> 1 + sum(0) [sum(4), sum(3), sum(2), sum(1)]
Step 5: sum(0) -> returns 0 [sum(4), sum(3), sum(2), sum(1), sum(0)]
Step 6: sum(1) -> returns 1 + 0 = 1 [sum(4), sum(3), sum(2), sum(1)]
Step 7: sum(2) -> returns 2 + 1 = 3 [sum(4), sum(3), sum(2)]
Step 8: sum(3) -> returns 3 + 3 = 6 [sum(4), sum(3)]
Step 9: sum(4) -> returns 4 + 6 = 10 [sum(4)]
Stack Size Limit
JavaScript engines have a maximum call stack size (typically 10,000 to 25,000 frames). Exceeding it throws a RangeError: Maximum call stack size exceeded. Read Preventing Stack Overflow in JavaScript Recursion to learn how to handle deep recursion safely.
Classic Examples
Factorial
Factorial of n (written n!) is the product of all positive integers up to n. Factorial is the textbook example of recursion because n! = n * (n-1)!
javascriptfunction factorial(n) {
// Base case
if (n <= 1) return 1;
// Recursive case: n! = n * (n-1)!
return n * factorial(n - 1);
}
console.log(factorial(5)); // 120 (5 * 4 * 3 * 2 * 1)
console.log(factorial(0)); // 1 (by definition)
console.log(factorial(1)); // 1
console.log(factorial(10)); // 3628800Fibonacci
Each Fibonacci number is the sum of the two preceding numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
javascriptfunction fibonacci(n) {
// Base cases
if (n === 0) return 0;
if (n === 1) return 1;
// Recursive case: fib(n) = fib(n-1) + fib(n-2)
return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(0)); // 0
console.log(fibonacci(1)); // 1
console.log(fibonacci(6)); // 8
console.log(fibonacci(10)); // 55Exponential Time Complexity
The naive Fibonacci recursion is very slow because it recalculates the same values repeatedly. fibonacci(40) makes over a billion function calls. Use memoization (caching) to fix this - see the optimization section below.
Power (Exponentiation)
javascriptfunction power(base, exponent) {
// Base case
if (exponent === 0) return 1;
// Recursive case: base^exp = base * base^(exp-1)
return base * power(base, exponent - 1);
}
console.log(power(2, 0)); // 1
console.log(power(2, 3)); // 8
console.log(power(5, 3)); // 125
console.log(power(10, 4)); // 10000Recursion with Data Structures
Array Sum
javascriptfunction sumArray(arr) {
// Base case: empty array
if (arr.length === 0) return 0;
// Recursive case: first element + sum of the rest
return arr[0] + sumArray(arr.slice(1));
}
console.log(sumArray([1, 2, 3, 4, 5])); // 15
console.log(sumArray([])); // 0Flatten Nested Arrays
javascriptfunction flatten(arr) {
let result = [];
for (const item of arr) {
if (Array.isArray(item)) {
// Recursive case: flatten nested array
result = [...result, ...flatten(item)];
} else {
// Base case: add non-array item
result = [...result, item];
}
}
return result;
}
console.log(flatten([1, [2, [3, [4]], 5], 6]));
// [1, 2, 3, 4, 5, 6]
console.log(flatten([[1, 2], [3, [4, [5]]]]));
// [1, 2, 3, 4, 5]Deep Clone
javascriptfunction deepClone(value) {
// Base cases: primitives and null
if (value === null || typeof value !== "object") {
return value;
}
// Recursive case: array
if (Array.isArray(value)) {
return value.map((item) => deepClone(item));
}
// Recursive case: object
const cloned = {};
for (const key in value) {
if (value.hasOwnProperty(key)) {
cloned[key] = deepClone(value[key]);
}
}
return cloned;
}
const original = { a: 1, b: { c: [1, 2, { d: 3 }] } };
const copy = deepClone(original);
copy.b.c[2].d = 999;
console.log(original.b.c[2].d); // 3 (unchanged)
console.log(copy.b.c[2].d); // 999Tree Traversal
Recursion naturally handles tree-shaped data because each node has children that are also nodes:
javascriptconst fileSystem = {
name: "root",
type: "folder",
children: [
{
name: "src",
type: "folder",
children: [
{ name: "index.js", type: "file", size: 1024 },
{ name: "utils.js", type: "file", size: 512 },
{
name: "components",
type: "folder",
children: [
{ name: "Header.js", type: "file", size: 768 },
{ name: "Footer.js", type: "file", size: 256 },
],
},
],
},
{ name: "README.md", type: "file", size: 2048 },
],
};
// Find all files recursively
function findFiles(node) {
if (node.type === "file") {
return [node.name];
}
// Recursively search all children and flatten results
return node.children.flatMap((child) => findFiles(child));
}
console.log(findFiles(fileSystem));
// ["index.js", "utils.js", "Header.js", "Footer.js", "README.md"]
// Calculate total size recursively
function totalSize(node) {
if (node.type === "file") {
return node.size;
}
return node.children.reduce((sum, child) => sum + totalSize(child), 0);
}
console.log(totalSize(fileSystem)); // 4608DOM Traversal
javascript// Find all text content in a DOM tree
function getAllText(element) {
// Base case: text node
if (element.nodeType === Node.TEXT_NODE) {
return element.textContent.trim();
}
// Recursive case: element with children
let texts = [];
for (const child of element.childNodes) {
const text = getAllText(child);
if (text) texts.push(text);
}
return texts.join(" ");
}Recursion vs Loops
Every recursive solution can be rewritten as a loop, and vice versa:
javascript// Recursive factorial
function factorialRecursive(n) {
if (n <= 1) return 1;
return n * factorialRecursive(n - 1);
}
// Iterative factorial (using a for loop)
function factorialIterative(n) {
let result = 1;
for (let i = 2; i <= n; i++) {
result *= i;
}
return result;
}
// Both return the same answer
console.log(factorialRecursive(5)); // 120
console.log(factorialIterative(5)); // 120| Feature | Recursion | Loop |
|---|---|---|
| Code readability | Often cleaner for tree/nested data | Often cleaner for linear data |
| Memory usage | One stack frame per call | Constant memory (usually) |
| Maximum depth | Limited by call stack (~10K) | No inherent limit |
| Performance | Can be slower (function call overhead) | Usually faster |
| Best for | Trees, graphs, nested structures | Arrays, ranges, counters |
| Risk | Stack overflow on deep recursion | Infinite loop on wrong condition |
When to Use Recursion
- Tree and graph traversal (DOM, file system, JSON)
- Problems that have a natural recursive structure (divide and conquer)
- When the recursive solution is significantly clearer than the iterative one
- Nested data of unknown depth
When to Use Loops
- Iterating over arrays
- Simple counting or accumulation
- Performance-critical code
- Very deep data (avoids stack overflow)
Optimizing Recursive Functions
Memoization
Cache results of previous calls to avoid redundant computation:
javascriptfunction fibonacciMemo(n, memo = {}) {
// Check cache
if (n in memo) return memo[n];
// Base cases
if (n === 0) return 0;
if (n === 1) return 1;
// Compute, cache, and return
memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
return memo[n];
}
console.log(fibonacciMemo(50)); // 12586269025 (instant!)
// Without memo: fibonacci(50) would take minutes| n | Calls without memo | Calls with memo |
|---|---|---|
| 10 | 177 | 19 |
| 20 | 21,891 | 39 |
| 30 | 2,692,537 | 59 |
| 40 | 331,160,281 | 79 |
| 50 | 40+ billion | 99 |
Generic Memoize Wrapper
javascriptfunction memoize(fn) {
const cache = new Map();
return function (...args) {
const key = JSON.stringify(args);
if (cache.has(key)) return cache.get(key);
const result = fn.apply(this, args);
cache.set(key, result);
return result;
};
}
const fibonacci = memoize(function (n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
});
console.log(fibonacci(100)); // 354224848179262000000 (instant)Tail Call Optimization
A tail call is when the recursive call is the very last operation in the function. Some engines can optimize this to avoid growing the stack:
javascript// NOT tail-recursive: n * factorial(...) is the last operation
function factorial(n) {
if (n <= 1) return 1;
return n * factorial(n - 1); // multiplication happens AFTER the call
}
// Tail-recursive: the recursive call IS the last operation
function factorialTail(n, accumulator = 1) {
if (n <= 1) return accumulator;
return factorialTail(n - 1, n * accumulator); // nothing after the call
}TCO Support is Limited
Tail Call Optimization (TCO) is part of the ES6 specification, but only Safari implements it. V8 (Chrome, Node.js) and SpiderMonkey (Firefox) do not. In practice, use iterative solutions or trampolines for deep recursion in most JavaScript environments.
Practical Examples
String Reversal
javascriptfunction reverseString(str) {
// Base case
if (str.length <= 1) return str;
// Recursive case: last char + reverse of the rest
return str[str.length - 1] + reverseString(str.slice(0, -1));
}
console.log(reverseString("hello")); // "olleh"
console.log(reverseString("a")); // "a"
console.log(reverseString("")); // ""Palindrome Check
javascriptfunction isPalindrome(str) {
// Normalize: lowercase, remove non-alphanumeric
const clean = str.toLowerCase().replace(/[^a-z0-9]/g, "");
function check(s) {
// Base cases
if (s.length <= 1) return true;
if (s[0] !== s[s.length - 1]) return false;
// Recursive case: check inner substring
return check(s.slice(1, -1));
}
return check(clean);
}
console.log(isPalindrome("racecar")); // true
console.log(isPalindrome("A man, a plan, a canal: Panama")); // true
console.log(isPalindrome("hello")); // falseNested Object Search
javascriptfunction findByKey(obj, targetKey) {
for (const key in obj) {
if (key === targetKey) return obj[key];
if (typeof obj[key] === "object" && obj[key] !== null) {
const result = findByKey(obj[key], targetKey);
if (result !== undefined) return result;
}
}
return undefined;
}
const data = {
user: {
profile: {
settings: {
theme: "dark",
notifications: { email: true },
},
},
},
};
console.log(findByKey(data, "theme")); // "dark"
console.log(findByKey(data, "email")); // true
console.log(findByKey(data, "missing")); // undefinedGenerate Permutations
javascriptfunction permutations(arr) {
// Base case: single element
if (arr.length <= 1) return [arr];
const result = [];
for (let i = 0; i < arr.length; i++) {
const current = arr[i];
const remaining = [...arr.slice(0, i), ...arr.slice(i + 1)];
const perms = permutations(remaining);
for (const perm of perms) {
result.push([current, ...perm]);
}
}
return result;
}
console.log(permutations([1, 2, 3]));
// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]Common Mistakes
1. Missing or Wrong Base Case
javascript// BUG: no base case - infinite recursion!
function count(n) {
console.log(n);
count(n + 1); // never stops
}
// BUG: base case never reached
function countdown(n) {
if (n === 0) return; // what if n is negative or a float?
console.log(n);
countdown(n - 1);
}
countdown(-5); // infinite recursion!
// FIX: robust base case
function countdown(n) {
if (n <= 0) return; // handles negatives and zero
console.log(n);
countdown(n - 1);
}2. Not Making Progress Toward Base Case
javascript// BUG: passes the same argument each time
function broken(arr) {
if (arr.length === 0) return [];
return [arr[0], ...broken(arr)]; // should be arr.slice(1)!
}3. Ignoring Return Values
javascript// BUG: forgot to return the recursive result
function find(arr, target) {
if (arr.length === 0) return -1;
if (arr[0] === target) return 0;
const result = find(arr.slice(1), target);
// Forgot: return result === -1 ? -1 : result + 1;
}
Rune AI
Key Insights
- Two parts: every recursive function needs a base case and a recursive case
- Make progress: each recursive call must move closer to the base case
- Call stack: each call adds a frame; too many causes stack overflow
- Memoize: cache results to avoid exponential redundant calls (Fibonacci, etc.)
- Trees are natural fits: file systems, DOM, nested JSON all suit recursion
- Loops for linear data: arrays and ranges are usually better served by iteration
Frequently Asked Questions
Is recursion faster than loops?
What is the maximum recursion depth in JavaScript?
Can every recursive function be written as a loop?
When should I use recursion over a loop?
Conclusion
Recursion is a function calling itself to solve smaller instances of the same problem. Every recursive function needs a base case that stops the recursion and a recursive case that makes progress toward that base case. Recursion excels at processing tree-shaped and nested data structures but uses more memory than loops due to call stack frames. Optimize with memoization to avoid redundant calculations. Use recursion when the problem naturally decomposes into sub-problems, and prefer iterative approaches when working with linear data or when stack depth is a concern.
More in this topic
OffscreenCanvas API in JS for UI Performance
Master the OffscreenCanvas API to offload rendering from the main thread. Covers worker-based 2D and WebGL rendering, animation loops inside workers, bitmap transfer, double buffering, chart rendering pipelines, image processing, and performance measurement strategies.
Advanced Web Workers for High Performance JS
Master Web Workers for truly parallel JavaScript execution. Covers dedicated and shared workers, structured cloning, transferable objects, SharedArrayBuffer with Atomics, worker pools, task scheduling, Comlink RPC patterns, module workers, and performance profiling strategies.
JavaScript Macros and Abstract Code Generation
Master JavaScript code generation techniques for compile-time and runtime metaprogramming. Covers AST manipulation, Babel plugin authorship, tagged template literals as macros, code generation pipelines, source-to-source transformation, compile-time evaluation, and safe eval alternatives.