cf.completefrontend
FOUNDATIONS · FOUNDATION

Recursion

A function solves a problem by calling itself on a smaller piece of the same problem.

Time O(n)Space O(d)11 practice problemsStep-through picture

The idea

A recursive function is a function that calls itself. It solves a big problem by handing a smaller copy of the same problem to another call of itself, then using that answer.

Every recursive function has two parts. The base case is an input so small that the answer is obvious, so the function returns it right away without calling itself. The recursive case breaks the input into smaller pieces, calls itself on each piece, and combines the results.

Recursion fits data that contains smaller copies of itself: a folder holds folders, a DOM element holds elements, a comment has replies that have replies. The code here adds up all the numbers in an array that may contain other arrays, however deep they go.

An everyday example

Counting the boxes inside boxes

You get a big box of gifts. Some things inside are gifts, and some are smaller boxes that hold more gifts and more boxes. To count the total value, you take out each thing. If it is a gift, you write down its value. If it is a box, you ask a helper to count that box and tell you its total, and the helper follows the very same rules. When every helper reports back, you add up their totals.

How the example maps to the code
In the exampleIn the code
A gift with a price tagThe base case: value is a number, so return value
A box with more things insideThe recursive case: value is an array
Asking a helper to count a smaller boxsumNested(item)
Adding up what every helper reportstotal += sumNested(item)
The array [4, [7, [-2]], []] drawn as boxes. The big box holds a gift worth 4, a middle box, and an empty box. The middle box holds a gift worth 7 and a small box. The small box holds a gift worth -2.47-2[-2][7, [-2]]empty[][4, [7, [-2]], []]
Each gift is a number and each box is an array. Opening a box gives you the same kind of problem again, just smaller: [7, [-2]] is a box of gifts and boxes, like the big one. The total is 4 + 7 + -2 = 9.

From the slow way to recursion

  1. Start with the obvious way. For an array with one level of nesting, like [4, [7, 1]], write a loop and, inside it, a second loop for inner arrays. For two levels you need a third loop, for three levels a fourth. You can't know the depth before the data arrives, so no fixed number of loops is enough.
  2. Now look at the inner array [7, [-2]] inside [4, [7, [-2]], []]. It is the same kind of thing as the outer one: an array whose items are numbers or more arrays. Its sum follows exactly the same rules. So a function that can sum any nested array can also sum each of its pieces.
  3. That gives the key move: write sumNested(value) as if it already works on smaller inputs. For each item, call sumNested(item) and trust the answer, the same way you trust Math.max without reading its code. All you have to write is how to combine the pieces: add them into total.
  4. The trust needs a floor, or the calls never stop. Some input must be small enough to answer without calling yourself. A plain number has nothing inside it, so its sum is itself. A base case for numbers plus a recursive case for arrays, each call working on a smaller piece: that function is recursion.
Left, the base case: a gift worth -2 is a number, so the function returns -2 straight away. Right, the recursive case: the box [7, [-2]] is an array, so the function calls sumNested(7) and sumNested([-2]) and adds the answers, 7 + -2 = 5.base case-2-2a number hasnothing inside, soreturn it as it isrecursive case7[-2][7, [-2]]sumNested(7)sumNested([-2])7 + -2 = 5
The base case answers without calling again. The recursive case asks the same function about each smaller piece, trusts the answers, and adds them up.

How it works

  1. Decide what one call returns for one input value. Here: the sum of every number inside value.
  2. Write the base case first: if value is a plain number, return it. It has nothing inside it to break down.
  3. Otherwise value is an array. Start total at 0.
  4. For each item in the array, call sumNested(item). Trust it to return that item's full sum, however deep it goes.
  5. Add each result to total, then return total.
  6. Each call works on a smaller piece than the one before, so the calls always reach base cases and finish.
The calls for sumNested([4, [7, [-2]], []]) drawn as a tree. The first call calls itself on 4, on [7, [-2]], and on []. The call on [7, [-2]] calls itself on 7 and on [-2], and the call on [-2] calls itself on -2. Answers go back up: -2, then -2 and 7 make 5, and 4, 5, and 0 make 9.[4, [7, [-2]], []]4[7, [-2]][]7[-2]-2↑ 4↑ 5↑ 0↑ 7↑ -2↑ -2= 9shaded: an array, calls againplain: a number, the base case
Every card is one call of sumNested. Arrows are calls going down. Shaded cards are arrays, so they call again; plain cards are numbers, the base case. The green answers travel back up, and each call adds what its children return: 4 + 5 + 0 = 9.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function sumNested(value) {
  2. if (!Array.isArray(value)) {
  3. return value;
  4. }
  5. let total = 0;
  6. for (const item of value) {
  7. total += sumNested(item);
  8. }
  9. return total;
  10. }

How fast it is

TimeO(n)
Extra memoryO(d)

Every number and every array is visited exactly once, where n counts both. The call stack holds one waiting call per level of nesting, so the extra memory is the depth d.

  • Best caseO(1)

    value is a plain number, such as sumNested(5): the base case returns at once without any loop.

  • Average caseO(n)

    Any nested array: every number and every array, n of them in total, is visited by exactly one call, and each call does a constant amount of work per item.

  • Worst caseO(n)

    The time never gets worse than one visit per piece. The shape matters for memory instead: a long chain like [[[[1]]]] is still O(n) time but uses the most stack space.

The call stack at the deepest moment. From the bottom: the first call on [4, [7, [-2]], []] waits with total 4, the call on [7, [-2]] waits with total 7, the call on [-2] waits with total 0, and the newest call, on -2, is running and returns -2. Four calls for four levels of nesting.newestfirst-2running: returns -2[-2]waiting, total = 0[7, [-2]]waiting, total = 7[4, [7, [-2]], []]waiting, total = 44 levels deep, 4 calls
At the deepest point four calls are on the stack at once, one per level of nesting, and each keeps its own total. That pile is the extra memory: it grows with the depth d, so the space is O(d).

Common mistakes

  • Forgetting the base case, or writing one that is never reached. The function calls itself forever and the page throws "Maximum call stack size exceeded".
  • Calling itself on an input that isn't smaller, such as sumNested(value) instead of sumNested(item). Make sure every call moves toward the base case.
  • Ignoring the return value. Writing sumNested(item); without total += throws the inner result away.
  • Sharing one variable between all calls, such as a total declared outside the function. Each call should keep its own state or return its result.
Calls of sumNested(value) on the same value pile up higher and higher, because none of them reaches a base case. An arrow leads to the console, which shows RangeError: Maximum call stack size exceeded.⋮sumNested(value)sumNested(value)sumNested(value)sumNested(value)same input, never smallerconsoleRangeError:Maximum call stacksize exceeded
Calling sumNested(value) instead of sumNested(item) passes the same input down, so no call ever reaches a number. The pile grows until the browser stops it with a RangeError.

When to use it

Look for these clues in a problem:

  • The data is nested: trees, folders, menus, comment threads, JSON, or the DOM.
  • The problem can be described in terms of a smaller version of itself, like "the size of a folder is the sum of the sizes inside it".
  • You need to try every choice, then every choice after that (backtracking builds on recursion).
  • The answer for n is defined using the answer for n - 1 or n / 2.

Check yourself

Answer each one in your head first, then open it.

What happens if you delete the base case?

A plain number reaches the loop, and for (const item of 4) throws a TypeError because numbers can't be looped over. Without a base case, recursion has no input it can answer directly.

Why doesn't the inner call's total overwrite the outer call's total?

Each call gets its own copy of its local variables. The outer call's total waits on the call stack until the inner call returns.

How many calls does sumNested([1, [2, [3]]]) make?

Six: one for each of the three arrays ([1, [2, [3]]], [2, [3]], and [3]) and one for each of the numbers 1, 2, and 3. That is one call per piece.

Why does the space depend on depth and not on the number of items?

Only calls that haven't returned yet take stack space. A flat array of a million numbers is only 2 calls deep at any moment, while a chain like [[[[1]]]] keeps every level waiting.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 11 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The claim is: sumNested(value) returns the sum of every number inside value. Prove it like climbing stairs, starting from the smallest inputs. For a plain number, the base case returns the number itself, which is its own sum. So the claim holds for the smallest inputs.

Now take an array, and assume the claim already holds for each of its items, because each item is smaller than the array that contains it. The loop adds the correct sum of every item into total, and the sum of an array is exactly the sum of its items' sums. So the claim holds for the array too. This step-by-step argument is called induction.

The calls always end, because every call works on an item strictly inside the current value. Real nested arrays have a finite depth, so each chain of calls reaches plain numbers or empty arrays, which return without calling again. If an array contained itself, that promise would break, and the calls would never end.

Going deeper

3 more ideas

Why it always finishes

Every recursive call works on a piece strictly inside the current value. Arrays can only be nested so deep, so the pieces keep getting smaller until they are plain numbers, which hit the base case and return without another call. If a recursive call ever got the same input back, it would call itself forever and crash with "Maximum call stack size exceeded".

The call stack keeps your place

When a function calls itself, JavaScript pauses the current call and puts a note on the call stack: which call it was in and what its variables held. When the inner call returns, the paused call picks up exactly where it stopped, with its own total. That is why each level keeps its own count without mixing them up.

Cost and the depth limit

The function visits every number and every array once, so the time is O(n) where n counts both. The extra space is the deepest chain of waiting calls, O(d) for nesting depth d. Browsers allow roughly ten thousand nested calls, so for very deep data (like a linked list with 100,000 nodes) rewrite the recursion as a loop with your own stack array.

Work it by hand

Every step in a table, with why

Add up a nested array three levels deep that also contains an empty array. Each row is one call starting, returning, or adding to its own total.

value = [4, [7, [-2]], []]

StepDepthCalltotalWhat happensWhy
10[4, [7, [-2]], []]0Array of 3 items: start total at 0The first call is not a number, so it skips the base case and loops over its 3 items.
214-Base case: return 44 is a plain number, so the call returns it at once without calling itself.
30[4, [7, [-2]], []]4total += 4The outer call picks up where it paused and adds the result.
41[7, [-2]]0New call with its own totalThe second item is an array, so a new call starts. Its total is separate from the outer call's total.
527-Base case: return 7Another plain number.
61[7, [-2]]7total += 7The middle call adds 7 and moves to its next item.
72[-2]0New call, one itemA one-item array still goes through the recursive case.
83-2-Base case: return -2This is the deepest point: four calls are on the call stack at once, three of them waiting.
92[-2]-2total += -2, return -2The array [-2] sums to -2. Negative numbers need no special handling.
101[7, [-2]]5total += -2, return 57 plus -2 is 5, and the middle call hands 5 back up.
110[4, [7, [-2]], []]9total += 5The outer call now has 4 + 5 = 9.
121[]0Empty array: return 0The loop runs zero times, so the call returns its starting total, 0. No extra base case is needed for empty arrays.
130[4, [7, [-2]], []]9total += 0, return 9Every item is added, so the first call returns the answer.

It returns 9, the sum of 4, 7, and -2. The trace ends when the first call returns, after 7 calls in total: 3 base cases and 4 arrays.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
RecursionO(n)O(d)The data is nested, like JSON, the DOM, or a file tree, and the depth is reasonable. The code mirrors the shape of the data and is the easiest to read.
Loop with an explicit stackO(n)O(n)The data might be very deep, such as thousands of levels. The stack array lives in normal memory instead of the call stack, so it can't overflow at a few thousand levels. It can hold many waiting items at once, up to O(n).
Flatten first: value.flat(Infinity)O(n)O(n)A quick one-liner when you just need every number. It builds a new flat array of all the numbers before you add them, so it uses more memory.

Extra memory: O(d) for nesting depth d: each level has one call waiting on the call stack. For a flat array d is 1, but for a chain like [[[[1]]]] the depth equals n, so the worst case is O(n) space.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Recursion and the other approaches, on a scale where each line up is 10 times more steps.
  • Recursion, Loop with an explicit stack, Flatten first: value.flat(Infinity) O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Recursion101,0001 million
Loop with an explicit stack101,0001 million
Flatten first: value.flat(Infinity)101,0001 million

Inputs that need care

5 tricky inputs
An empty array, or empty arrays inside: [[], [[]]]
Each empty array's loop runs zero times and returns 0, so the whole call returns 0. The empty arrays need no special code.
A plain number instead of an array: sumNested(7)
It hits the base case and returns 7 at once.
Very deep nesting, thousands of levels
Each level adds a waiting call, and the engine has a limit. In one Node.js run, sumNested threw RangeError: Maximum call stack size exceeded at about 4,700 levels. For data that deep, use a loop with your own stack array.
An array that contains itself: const a = [1]; a.push(a);
sumNested(a) calls itself on a again and again, never reaching a base case, and crashes with the same stack error. If the data can have cycles, keep a Set of arrays already visited and skip them.
A string among the numbers: [1, "3"]
The base case returns "3" as it is, and total += "3" joins text, so the result is the string "13", not 4. Check typeof value === "number" or convert with Number if the data might hold strings.

Variations and follow-ups

Twists interviewers add

A loop with your own stack

Any recursion can be rewritten with a loop and an array used as a stack. Push the starting array; then pop an item, add it if it's a number, or push its items if it's an array. The work is the same, but the stack lives in normal memory, so very deep data doesn't crash.

Passing an accumulator

Instead of returning a sum and adding it, a helper can take the running total as a second argument and pass it down. When the recursive call is the very last thing a function does, this is called tail recursion. Most JavaScript engines don't reuse stack space for it, Safari being the exception, so it doesn't fix the depth limit in Chrome or Node.js.

Recursion with memoization

Some recursive functions call themselves on the same input many times, like computing Fibonacci numbers as fib(n - 1) + fib(n - 2). Saving each answer in a Map the first time turns an exponential number of calls into one per distinct input.

Splitting into halves

Divide and conquer, used by merge sort and binary search, is recursion where each call works on a half of the input. The depth is then only about log₂ n, so stack space is small even for millions of items.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it when the input contains smaller copies of itself: trees, nested lists, folders, or an answer defined from the answer for n - 1. Words like "nested", "children", or "any depth" are strong hints.
  • Explain it in two sentences before coding: "The base case is a plain number, which is its own sum. For an array, I trust the function to sum each item, then add those sums." That shows you understand the trust step.
  • Test by hand with three inputs: a single number, an empty array, and one item nested two levels deep. Walk the call stack out loud for the last one, the way the trace above does.
  • Expect the follow-up "what if the nesting is 100,000 levels deep?". The answer: recursion would overflow the call stack, so rewrite it as a loop with an array used as a stack, which has the same time and moves the memory off the call stack.

Where frontend code uses it

The same idea in real UI code
  • Walking the DOM: a function that visits an element and then calls itself on each of element.children reaches every element on the page.
  • React renders a component tree recursively: a component returns elements, and each of those components renders its own children the same way.
  • Deep-cloning or deep-comparing JSON objects (for state or caches) calls the same function on every nested object and array.
  • Building a nested sidebar menu or file tree from data where each item has a children array.

Related algorithms