Recursion Techniques Deep Dive
Master recursion: base cases, recursive cases, tail recursion, memoization, and the call stack.
What you'll learn
- Base case and recursive case design
- The call stack and stack overflow
- Tail recursion and its optimization
- Memoization to avoid redundant computation
Concept
Recursion Techniques Deep Dive
Recursion is when a function calls itself. It is a natural way to solve problems that have a self-similar structure - trees, fractals, divide-and-conquer algorithms. Every recursive function needs two parts: a base case (when to stop) and a recursive case (how to break the problem into a smaller one).
The Call Stack
Each recursive call adds a frame to the call stack, containing local variables and the return address. Deep recursion can overflow the stack - typically around 10,000 frames in JavaScript. This is why iterative solutions are preferred for very deep recursion.
Tail Recursion
A recursion is tail-recursive if the recursive call is the very last operation. Tail-recursive functions can be optimized by the compiler to use constant stack space (no new frame). JavaScript engines may optimize this in strict mode, but it is not guaranteed.
Memoization
Naive recursion often recomputes the same subproblems. The Fibonacci sequence fib(n) = fib(n-1) + fib(n-2) has O(2^n) calls without memoization but O(n) with it. Memoization caches results by input, turning exponential recursion into linear time.
Recursion vs Iteration
Every recursion can be converted to iteration using an explicit stack. Recursion is clearer when the problem is naturally recursive (tree traversal); iteration is better when depth is unbounded.
Example
// Naive recursion - exponential time!
function fibNaive(n) { if (n <= 1) return n; return fibNaive(n-1) + fibNaive(n-2); }
// Memoized recursion - linear time
const memo = new Map();
function fibMemo(n) {
if (n <= 1) return n;
if (memo.has(n)) return memo.get(n);
const r = fibMemo(n-1) + fibMemo(n-2);
memo.set(n, r); return r;
}
// Tail-recursive - can be optimized to a loop
function fibTail(n, a = 0, b = 1) { if (n === 0) return a; return fibTail(n-1, b, a+b); }
console.log('Memo:', fibMemo(40));
console.log('Tail:', fibTail(40));
The naive version makes 2^n calls. Memoization caches each fib(k), reducing to n calls. The tail-recursive version carries accumulators a and b.
Try it
- JSON Formatter
Nested JSON is a recursive structure - formatting it requires recursive traversal.
Common mistakes
The mistake
Forgetting the base case, causing infinite recursion.
The fix
Every recursive function must have a base case that does not recurse. Without it, the function calls itself forever until stack overflow.
The mistake
Using naive recursion for problems with overlapping subproblems.
The fix
If the same subproblem is solved multiple times, add memoization. Fibonacci and many DP problems benefit enormously from caching.
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.