sdlc.dev

Data structures and algorithms path · Sequences · Topic 5 of 13

Recursion vs iteration

Not started

A recursive function solves a problem by calling itself on smaller pieces of it, until the pieces are small enough to answer directly. Behind the scenes every pending call sits on the call stack, waiting for the inner call to return. So recursion is iteration with a stack that the runtime manages for you, and you can always swap that hidden stack for one you manage yourself.

Why it matters: Trees, graphs, parsers and divide-and-conquer algorithms are clearest as recursion, and knowing how to turn it into a loop saves you when the input is deep.

  1. 1Base case and smaller case

    A recursive function handles a trivial input directly and reduces every other input to smaller versions of itself.

  2. 2Each call is a stack frame

    Pending calls wait on the call stack, so recursion depth costs memory, and the call stack is small.

  3. 3Deep input overflows

    Too many nested calls throw RangeError in JavaScript and RecursionError in Python (default limit 1000).

  4. 4Any recursion can be a loop

    Replace the call stack with an explicit stack (or queue) on the heap, and depth stops being a problem.

1

How it works

The explanation, with examples you can run.

The two parts

Every correct recursive function has a base case that it answers without recursing and a recursive case that moves strictly towards it. Summing a nested list is a natural fit, because the data is itself recursive: a list contains numbers or more lists.

⌘/Ctrl + Enter
OutputNot run yet

Press Run to see what your code prints, in order.

Runs in this browser, in an isolated frame with no access to this page. console.log, info, warn and error are shown; code runs as a classic script, so use an async function for await.

The iterative version does the same work in a different order: instead of the runtime remembering "I'm halfway through this list", the explicit stack holds the items not yet visited. Trees, file-system walks, JSON processing, parsers and divide-and-conquer sorts like merge sort and quicksort are all naturally written this way.

The cost: stack depth

Each call needs a stack frame for its arguments, locals and return address, and the call stack is small, under a megabyte in Node 22 (V8's --stack-size defaults to 864 KB there), far less than the heap. Python sets a recursion limit instead: sys.getrecursionlimit() returns 1000 by default, and exceeding it raises RecursionError. Recursion depth follows the shape of the input, so code that works on every test can overflow on one deeply nested document:

⌘/Ctrl + Enter
OutputNot run yet

Press Run to see what your code prints, in order.

Runs in this browser, in an isolated frame with no access to this page. console.log, info, warn and error are shown; code runs as a classic script, so use an async function for await.

Some languages guarantee tail call elimination: if the recursive call is the very last thing a function does, the runtime reuses the current frame. ES2015 actually specified proper tail calls for strict-mode JavaScript, but V8 (Chrome and Node) has them switched off, and CPython deliberately doesn't do it either, so in both languages deep recursion overflows no matter how you write it.

Choosing

Write the recursive version first when the problem is recursive: it is usually shorter and easier to get right. Switch to an explicit stack when depth depends on untrusted or unbounded input, such as user-supplied JSON, long linked structures, or graph searches over millions of nodes. Using a queue instead of a stack in the same loop changes depth-first order into breadth-first order, which is the subject of the graphs topic.

Recursion can also repeat work. A naive recursive Fibonacci recomputes the same values exponentially many times; caching the results, memoisation, fixes that and leads straight into dynamic programming.

2

Check yourself

3 questions. Get them all right to finish this topic.

  1. 1.What happens if a recursive function's base case can never be reached?
  2. 2.Does Node optimise tail calls so that `return f(n - 1)` uses no extra stack?
  3. 3.You convert a recursive depth-first traversal to a loop. What replaces the call stack?

0 of 3 right so far. Get all three to finish this topic.

Go deeper