Recursion for beginners: a function that calls itself (DSA in JavaScript)

The idea

A recursive function solves a problem by calling itself on a smaller version of the same problem. It keeps going until the problem is so small that the answer is known straight away.

Think of it like this: Russian nesting dolls. To count the dolls, open the outer one: the answer is 1 plus however many dolls are inside it. You keep opening until you reach the tiny doll that doesn't open. That's where you stop and start counting back out.

A function that calls itself

Recursion means a function calls itself. Each call works on a smaller input than the one before.

Take factorial: factorial(4) is 4 × 3 × 2 × 1 = 24. Notice that 4 × 3 × 2 × 1 is the same as 4 × factorial(3). So the function can hand the smaller part to itself:

function factorial(n: number): number {
  if (n <= 1) return 1;          // base case: small enough to answer directly
  return n * factorial(n - 1);   // recursive case: use the answer to a smaller problem
}

factorial(4); // 4 * factorial(3) = 4 * 6 = 24

The two parts every recursive function needs

Base case: the input that's so small you return the answer without calling yourself. For factorial, that's n <= 1, which returns 1. Without a base case the function calls itself forever.
Recursive case: make the input smaller, call yourself, and use the result. For factorial, that's n * factorial(n - 1).

Every recursive call must move closer to the base case. n - 1 does: 4, 3, 2, 1, stop.

The hardest part for beginners is trusting the smaller call. Don't try to follow every call in your head while writing. Assume factorial(n - 1) already returns the right answer, and ask: "if I had that, how do I finish the job for n?"

The call stack: going down and coming back up

When a function calls another function, the first one pauses and waits. JavaScript keeps the paused calls on the call stack. A stack is a pile where you can only add to or take from the top, like a pile of plates. The last call in is the first one to finish.

With recursion, the stack grows as calls go down to the base case. Then it shrinks on the way back up, as each call gets its answer and finishes. Step through factorial(3) below and watch the paused calls pile up on the stack, then come off it one by one.

Stack overflow

Each paused call takes a little memory, and the stack has a limit. In most JavaScript engines it's around 10,000 calls deep. Go past it and you get:

RangeError: Maximum call stack size exceeded

This is a stack overflow. Two common causes:

No base case, or a base case the input never reaches. factorial(-1) with a base case of n === 1 would go -2, -3, -4… forever. That's why the example uses n <= 1.
Input too deep. Recursing once per element over an array of 100,000 numbers overflows even with a correct base case. For a long flat list, a loop is the better tool.

Recursion also uses space: one stack frame per paused call. A stack frame is the memory that holds one call's variables while it waits. A recursion that goes n calls deep uses O(n) space, even if it creates no arrays.

When recursion is the natural tool

For a flat array, a loop is usually simpler. Recursion shines when the data is nested: things that contain smaller things of the same kind. Folders contain folders. Comments have replies, which have replies. A menu has sub-menus. A tree is a node with child nodes. Trees have their own lesson later.

You don't know how deep the nesting goes, so you can't write the right number of loops. A recursive function handles any depth, because each call deals with one level and hands the children to itself.

type Comment = { text: string; replies: Comment[] };

// How many comments in a thread, including all replies at any depth?
function countComments(c: Comment): number {
  let count = 1;                 // this comment
  for (const r of c.replies) {
    count += countComments(r);   // each reply is a smaller thread of the same shape
  }
  return count;                  // base case is hidden: no replies means the loop doesn't run
}

Three questions to write any recursive function

What's the smallest input, and what's its answer? That's your base case. Examples: an empty array, n <= 1, a comment with no replies.
How do I make the input smaller? Examples: n - 1, the next index, each child.
If the smaller call already gave me the right answer, how do I finish? Examples: multiply by n, add 1, add up the children.

Write the base case first, as the first line of the function. Then write the recursive case.

Common mistakes

No base case, or one the input skips past, such as n === 0 when n can start negative. Symptom: Maximum call stack size exceeded.
Forgetting return on the recursive call: factorial(n - 1); on its own line. The result is thrown away and the function returns undefined.
Not making the input smaller: calling f(n) from inside f(n). It never reaches the base case.
Passing arr.slice(1) on every call. Each slice copies the array, so the total becomes O(n²). Pass an index instead: f(arr, i + 1).
Using recursion on a very long flat list, such as 100,000 items. It overflows the stack. Use a loop.