Recursion
A recursive function solves a small piece and hands the rest to a call of itself. Each call waits on the call stack until the one it made returns. When the smallest case answers directly, the waiting calls finish one by one, newest first.
47295
i
call stack: oldest call on the left, the running one on the right
sum(0)
Call sum(0): add up a[0] and everything after it.
1function sum(a, i = 0) {2 if (i === a.length) return 0;3 const rest = sum(a, i + 1);4 return a[i] + rest;5}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n | one call per item, plus the base case |
| average | n | every input |
| worst | n | every input |
| space | n | every waiting call stays on the stack |
Where it breaks
- No base case. Without
if (i === a.length) return 0the calls never stop, and the program crashes with a stack overflow. - Deep input. Every waiting call takes stack memory. Summing a million items this way overflows the stack in most languages, while a plain loop needs no stack at all. Python stops at about 1,000 calls by default.
- The work happens on the way back. Pick Five items and watch: no addition happens until the base case returns 0. Then each call adds its item as the stack unwinds.