Recursion

A function that calls itself

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem, again and again, until the problem is small enough to answer directly. Picture a set of Russian nesting dolls: to open them all, you open one doll, then do the exact same thing to the smaller doll inside — and you stop when you reach the tiny solid doll that does not open.

Every correct recursive function has two parts, and you must always write both:

• A base case — the simplest version that has a direct answer and stops the recursion (the tiny solid doll).
• A recursive case — where the function calls itself on a smaller input, moving towards the base case.

Worked example: factorial

A classic is the factorial of a number — written n! — which means multiply every whole number from n down to 1. For example 4! = 4 × 3 × 2 × 1 = 24. Notice the self-similar shape: 4! is just 4 × 3!, and 3! is 3 × 2!, and so on. That "the answer uses a smaller answer of the same kind" is exactly what recursion captures.

<script>
  function factorial(n) {
    if (n <= 1) return 1;          // base case: stop here
    return n * factorial(n - 1);   // recursive case: smaller problem
  }
  document.write("4! = " + factorial(4));
</script>

The first line is the base case: when n reaches 1 (or below), the answer is simply 1 and we stop calling. The second line is the recursive case: the answer for n is n times the factorial of n - 1, a slightly smaller problem each time.

Trace factorial(4) as the calls stack up and then unwind:

1. factorial(4) needs 4 * factorial(3) — so it pauses and calls factorial(3).
2. factorial(3) needs 3 * factorial(2) — it pauses and calls factorial(2).
3. factorial(2) needs 2 * factorial(1) — it pauses and calls factorial(1).
4. factorial(1) hits the base case and returns 1 directly — no more calls.
5. Now the paused calls finish in reverse: 2 * 1 = 2, then 3 * 2 = 6, then 4 * 6 = 24.

Where recursion really shines: nested data

Loops are fine for flat lists, but recursion is the natural fit when data is nested to an unknown depth — folders inside folders, comments with replies, or a tree. Here we add up numbers in an array that contains other arrays, however deeply they nest.

<script>
  function deepSum(list) {
    let total = 0;
    for (const item of list) {
      if (Array.isArray(item)) {
        total += deepSum(item);   // item is a nested array → recurse
      } else {
        total += item;            // a plain number → just add it
      }
    }
    return total;
  }

  document.write(deepSum([1, [2, 3, [4, 5]], 6]));
</script>

For each item, we ask "is this itself an array?". If it is a plain number, we add it. If it is a nested array, we call deepSum on that inner array — the same function handling a smaller piece. This naturally dives into [4, 5] inside [2, 3, [4, 5]] no matter how deep the nesting goes, which a single simple loop cannot do.