Skip to content

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.

View glossary

Build real projects

Apply what you learned by building guided projects with starter code and solutions.

View projects

Decode error messages

Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.

View errors