Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 156 ยท Functions

Recursion

Learn recursion in JavaScript - write base cases, trace the call stack, walk nested trees, compare recursion with loops and avoid stack overflow errors.

A recursive function is a function that calls itself. Instead of solving a whole problem at once, it solves a small piece and hands the rest โ€” a smaller version of the same problem โ€” to another call of itself. Eventually the problem becomes so small that the answer is obvious, and the calls stop.

Recursion is the natural tool for data that contains smaller copies of itself: folders inside folders, comments with replies to replies, menus with submenus, or the DOM tree of a web page. For simple counting, a loop is usually clearer. This lesson shows how to write recursive functions correctly, how they use the call stack, and how to choose between recursion and loops.

The two parts of every recursive function

Every recursive function needs:

  1. A base case โ€” a condition where the function returns an answer directly, without calling itself.
  2. A recursive case โ€” the function calls itself with a smaller or simpler input, moving toward the base case.

If either part is missing or wrong, the function never stops. Here is a countdown written both ways:

JS Countdown: loop vs recursion

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Both print the same thing. The recursive version expresses the idea as "print this number, then count down from one less", and "counting down from zero" is simply liftoff.

Recursion that returns values

Most recursive functions compute something. The trick is to trust that the smaller call returns the right answer, and build your answer from it. The classic example is the factorial: 5! is 5 ร— 4 ร— 3 ร— 2 ร— 1, which is the same as 5 ร— 4!.

JS Factorial and sum, step by step

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The trace shows the shape of every recursive computation. The calls go down, each waiting for the one below it. When the base case returns, the results come back up, and each waiting call finishes its multiplication. (const [first, ...rest] is destructuring; it takes the first item and collects the rest into a new array.)

Thinking recursively in three steps

When you write a recursive function, ask these three questions in order:

  1. What is the smallest input I can answer immediately? An empty array, the number 0, a folder with no subfolders. That becomes your base case.
  2. How do I make the input smaller? Drop the first item, subtract one, move to the children. Each recursive call must get closer to the base case.
  3. If the smaller call gives me the right answer, how do I build my answer from it? Add the first item to the sum of the rest, multiply n by the factorial of n - 1.

The third step is where people get stuck, because it feels like cheating to assume the smaller call works. It isn't: if the base case is right and every step moves toward it, the assumption holds all the way down.

The call stack

Each function call gets a stack frame: a small record holding its parameters, local variables and the place to continue when it returns. Frames are stacked on top of each other, and only the top one is running. When traced(4) calls traced(3), the frame for traced(4) waits underneath until traced(3) is done.

The stack has a limited size. If recursion goes too deep โ€” usually because the base case is missing or never reached โ€” the engine throws a RangeError:

JS Stack overflow

Press Run (or Ctrl + Enter) to see the console output here.

No output.

In Chromium-based browsers the message is "Maximum call stack size exceeded"; Firefox throws an InternalError with "too much recursion" instead. The exact limit depends on the browser and on how much each frame stores, but it is typically in the thousands to tens of thousands of calls.

Don't count on tail-call optimization. The language specification describes "proper tail calls", which would let some recursive calls run without growing the stack. In practice only Safari implements them, so in Chrome, Firefox and Node.js deep recursion always uses one frame per call. For data that can be very deep or very long, use a loop.

Walking trees

Recursion really shines with nested structures, where you don't know in advance how deep the nesting goes. A loop alone can't easily follow branches of unknown depth, but a recursive function just handles one level and calls itself for each child.

JS Totals and printing in a folder tree

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Notice there is no explicit if for the base case here. A folder without subfolders is the base case: the for loop over folder.folders simply runs zero times, and the function returns.

The same idea flattens arbitrarily nested arrays:

JavaScript
function flatten(items) {
  const result = [];
  for (const item of items) {
    if (Array.isArray(item)) result.push(...flatten(item));
    else result.push(item);
  }
  return result;
}

flatten([1, [2, [3, [4]], 5]]); // [1, 2, 3, 4, 5]

Arrays have a built-in flat(Infinity) for this exact job (see Array Recipes), but the recursive version shows how such tools work. Walking the DOM tree uses the very same pattern.

Recursion vs loops

Anything you can write with recursion, you can also write with a loop (sometimes with an explicit stack array), and vice versa. Choose the one that makes the code clearer:

  • Use a loop for straight sequences: counting, summing a flat list, repeating until a condition is met. Loops use no extra stack and are usually faster.
  • Use recursion for branching, nested data: trees, nested comments, file systems, parsing nested expressions, and "try every option" searches.

Some recursive solutions repeat the same work many times. The naive Fibonacci function calls itself twice per step, so the number of calls explodes:

JS Fibonacci: naive, remembered and iterative

Press Run (or Ctrl + Enter) to see the console output here.

No output.

fibSlow(25) needs over 240,000 calls. The memoized version computes each value once, and the loop needs no stack at all. (Above fib(78) the results exceed Number.MAX_SAFE_INTEGER, so fib(90) is close but not exact; BigInt would fix that.)

Debugging recursion: add a depth parameter and indent your console.log output with it, as in the traced example. Seeing the calls go down and come back up makes most bugs obvious.

Recursion exercises

Six classic problems, each with a short solution. Try to write your own version before you read the code, and always name the base case and the smaller problem first.

  1. Power. power(base, exp) for a non-negative integer exp. The simple version multiplies exp times; splitting the exponent in half needs only about log2(exp) calls, because x^n = (x^(n/2))^2.
  2. Print n times. Print a message n times with no loop: print once, then solve the same problem for n - 1.
  3. Permutations of a string. Fix each character in turn as the first one and permute the rest.
  4. Subset sums. List the sum of every subset of an array. For each item you either skip it or take it, so the answers for the whole array are the answers for the rest, with and without the first item added.
  5. Fewest perfect squares. The smallest count of perfect squares (1, 4, 9, ...) that add up to n. Try each square s <= n as one piece and recurse on n - s, remembering results so each n is solved once.
  6. Slow sort. A deliberately inefficient algorithm whose structure is purely recursive: sort both halves, move the larger of the two halves' maximums to the end, then slow-sort everything except that last element. It teaches recursion, but never use it for real work.
JS Six recursion exercises

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Notice how each solution has exactly the shape from the top of this lesson: one or two base cases, then a call on a smaller input. Exercise 3 has n! results and exercise 4 has 2^n, so these two explode quickly on long inputs; that growth is a property of the problem, not of recursion.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the job of the base case in a recursive function?

    Without a base case that is eventually reached, the function calls itself forever until the stack overflows.
  2. 2. What does f(3) return? function f(n) { if (n === 0) return 0; return n + f(n - 1); }

    f(3) = 3 + f(2) = 3 + 2 + f(1) = 3 + 2 + 1 + f(0) = 6.
  3. 3. What happens in Chrome when a recursive function never reaches its base case?

    Each call adds a stack frame. When the stack is full, the engine throws instead of hanging.
  4. 4. Which task is the best fit for recursion?

    Nested data of unknown depth is where recursion is clearest. The others are simple sequences that suit a loop.
  5. 5. Why is the naive recursive Fibonacci function slow?

    The number of calls grows exponentially. Memoization or a loop computes each value only once.

Summary

  • A recursive function calls itself on a smaller problem until it reaches a base case it can answer directly.
  • Calls stack up on the call stack; results come back up as each call returns.
  • Too-deep recursion throws a RangeError (an InternalError in Firefox); don't rely on tail-call optimization.
  • Recursion is ideal for trees and nested data; loops are better for simple sequences and very deep or long inputs.
  • Repeated work can be removed with memoization, using a Map to remember computed results.

Next: The this Keyword โ€” how JavaScript decides which object a function is working with.