What Is Recursion? Explained With Simple Real-Life Examples + Code
Recursion is a function that calls itself. That sounds circular — because it is. The key is knowing when to stop. This guide explains recursion through analogies, walks through the call stack visually, and shows you when to use it (and when not to).
2
components every recursive function must have
O(n)
stack frames consumed for depth-n recursion
∞
stack overflow if base case is missing
3
classic examples: factorial, Fibonacci, trees
The Real-Life Analogy
Imagine you're standing in a line and ask the person in front of you: "What position am I?" They don't know, so they ask the person in front of them. That person asks the next, and so on — until someone at the front says "I'm position 1." That answer ripples back: "I'm 2", "I'm 3"... until it reaches you. That's recursion.
The two required parts
Every recursive solution has two parts: a base case (the stop condition — "I'm position 1, I know the answer") and a recursive case (the self-referential step — "I'm 1 + whatever the person in front of me says"). Missing either one breaks the recursion entirely.
The Simplest Possible Example: Countdown
// ITERATIVE version (loop)
function countdownLoop(n) {
for (let i = n; i >= 0; i--) {
console.log(i);
}
}
// RECURSIVE version — does the exact same thing
function countdownRecursive(n) {
if (n < 0) return; // BASE CASE: stop when n goes negative
console.log(n);
countdownRecursive(n - 1); // RECURSIVE CASE: call self with smaller n
}
// Both print: 5, 4, 3, 2, 1, 0
countdownRecursive(5);countdownRecursive(5)
Prints 5, then calls countdownRecursive(4). Waits for it to return before continuing.
countdownRecursive(4)
Prints 4, then calls countdownRecursive(3). Now 2 frames on the call stack.
countdownRecursive(3)
Prints 3, then calls countdownRecursive(2). 3 frames deep.
countdownRecursive(2)
Prints 2, then calls countdownRecursive(1). 4 frames deep.
countdownRecursive(1)
Prints 1, then calls countdownRecursive(0). 5 frames deep.
countdownRecursive(0)
Prints 0, then calls countdownRecursive(-1). 6 frames deep.
countdownRecursive(-1)
n < 0 → BASE CASE → returns immediately. All 6 frames unwind in sequence.
Classic Example: Factorial
5! (factorial) = 5 × 4 × 3 × 2 × 1 = 120. This is naturally recursive: 5! = 5 × 4!. The problem breaks into a smaller version of itself — the hallmark of a recursive problem.
function factorial(n) {
if (n <= 1) return 1; // BASE CASE: 0! = 1! = 1
return n * factorial(n - 1); // RECURSIVE CASE: n! = n × (n-1)!
}
// How factorial(4) unfolds on the call stack:
// factorial(4)
// = 4 * factorial(3)
// = 4 * (3 * factorial(2))
// = 4 * (3 * (2 * factorial(1)))
// = 4 * (3 * (2 * 1)) ← base case reached, unwinding begins
// = 4 * (3 * 2)
// = 4 * 6
// = 24
console.log(factorial(5)); // → 120
console.log(factorial(0)); // → 1 (base case)Where Recursion Really Shines: Tree Traversal
Loops are for flat data; recursion is for nested data
// File system tree
const fileSystem = {
name: 'root',
children: [
{ name: 'src', children: [
{ name: 'index.js', children: [] },
{ name: 'utils', children: [
{ name: 'helper.js', children: [] }
]}
]},
{ name: 'package.json', children: [] },
]
};
// Recursive: naturally mirrors the tree structure — no manual stack needed
function printTree(node, depth = 0) {
console.log(' '.repeat(depth) + node.name);
for (const child of node.children) {
printTree(child, depth + 1); // recurse into each child
}
}
printTree(fileSystem);
// root
// src
// index.js
// utils
// helper.js
// package.json
// Counting all files recursively:
function countFiles(node) {
if (node.children.length === 0) return 1; // leaf node = file
return node.children.reduce((sum, child) => sum + countFiles(child), 0);
}
console.log(countFiles(fileSystem)); // 3 (index.js, helper.js, package.json)The Stack Overflow Problem
Missing base case — stack overflow
// Missing base case → infinite recursion → stack overflow!
function countDown(n) {
console.log(n);
countDown(n - 1); // No stop condition — calls itself forever
}
// RangeError: Maximum call stack size exceeded
// JavaScript allows ~10,000-15,000 frames before crashingBase case prevents infinite recursion
// Base case stops the recursion before the stack overflows
function countDown(n) {
if (n <= 0) return; // ← base case: stop here
console.log(n);
countDown(n - 1);
}
// If you genuinely need deep recursion (>10,000 levels),
// convert to iterative with an explicit stack array insteadFibonacci: Naive vs Memoized
Naive O(2ⁿ) — exponentially slow
// Naive Fibonacci — O(2ⁿ) exponential time — catastrophically slow
function fib(n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2); // recomputes same values millions of times
}
// fib(40) → ~1 billion recursive calls
// fib(50) takes seconds; fib(100) practically never finishes
// fib(40) recalculates fib(2) over 100 million times!Memoized O(n) — linear, instant
// Memoized Fibonacci — O(n) linear time — fast for any n
function fib(n, memo = {}) {
if (n <= 1) return n;
if (memo[n] !== undefined) return memo[n]; // return cached result
memo[n] = fib(n - 1, memo) + fib(n - 2, memo); // cache before returning
return memo[n];
}
// fib(1000) returns instantly — each value computed exactly once
console.log(fib(50)); // 12586269025Recursion vs Iteration
| Item | Recursion | Iteration (loops) |
|---|---|---|
| Best for | Trees, graphs, divide-and-conquer, backtracking | Linear sequences, simple counting, array processing |
| Stack usage | O(depth) call stack frames — limited to ~10K deep | O(1) constant stack — no depth limit |
| Readability | Often more elegant for nested/hierarchical data | More explicit, easier to trace line by line |
| Overflow risk | Stack overflow if depth > ~10,000 (language-dependent) | No overflow risk — loop runs indefinitely |
| Performance | Function call overhead per level | Slightly faster — no call overhead |
| Debugging | Harder — must trace call stack mentally | Easier — sequential, straightforward to trace |
Tail Recursion — Optimized Recursion
// NOT tail-recursive: multiplication happens AFTER the recursive call returns
function factorial(n) {
if (n <= 1) return 1;
return n * factorial(n - 1); // n * ... requires waiting for the recursive result
}
// Tail-recursive: accumulator carries the running result
// The recursive call is the VERY LAST thing — no work after it
function factorialTail(n, acc = 1) {
if (n <= 1) return acc; // base case: return accumulated result
return factorialTail(n - 1, n * acc); // multiply into acc BEFORE calling
}
// factorialTail(5):
// → factorialTail(4, 5)
// → factorialTail(3, 20)
// → factorialTail(2, 60)
// → factorialTail(1, 120) → 120
// Some engines (Scheme, Proper Tail Calls in V8 strict mode) optimize
// tail-recursive calls to use O(1) stack space instead of O(n)Merge Sort (Divide and Conquer)
Recursively splits the array in half, sorts each half, then merges. O(n log n) — the standard fast sort. Each recursive call works on a smaller subarray until single-element base case.
Binary Search (Recursive)
Check the middle element — if target is less, recurse left half; if more, recurse right half. O(log n). Elegant recursive solution that mirrors the mental model of divide-and-conquer search.
Backtracking (Permutations/Sudoku)
Try a choice, recurse, and if it leads to a dead end, undo (backtrack) and try another choice. Used for Sudoku solvers, N-queens, maze solving — problems where you explore a decision tree.
JSON Deep Clone/Traverse
Recursively traverse any JSON structure — arrays, objects, nested values — without knowing the depth in advance. Each value is either a leaf (primitive) or a node (object/array) that recurses further.