Base cases and the call stack

Recursion feels like magic until you see where the intermediate work actually lives: the call stack.

Each call gets its own frame

Every time a function is called, the program pushes a stack frame holding that call's local variables and its place in the code. When the call returns, its frame gets popped. With recursion, many frames for the same function pile up at once.

For sumTo(3) the stack grows:

sumTo(3)  waiting on sumTo(2)
  sumTo(2)  waiting on sumTo(1)
    sumTo(1)  waiting on sumTo(0)
      sumTo(0) = 0      <- base case, returns
    sumTo(1) = 1 + 0
  sumTo(2) = 2 + 1
sumTo(3) = 3 + 3 = 6

The calls unwind in reverse order: the deepest call (the base case) resolves first, and each caller finishes as its callee returns.

Why you always need a base case

Without one — or with a recursive step that doesn't shrink the input — frames pile up forever until the program runs out of stack space (a stack overflow). Two rules keep you safe:

Handle the smallest input(s) directly and return.
Make every recursive call move toward a base case (smaller n, shorter string, fewer elements).

Cost

Depth d of recursion means up to d frames alive at once, so recursion uses O(d) space on the stack even when the logic looks like it uses no extra memory. Keep that in mind when you compare a recursive solution to a loop.

With a base case, a shrinking step, and an eye on depth, you're ready for the warm-ups that follow.