Recursion and the call stack

Overview

Explains how a function that calls itself terminates and how the call stack tracks progress.

Every recursive routine needs at least one base case that returns without recursing, and every recursive call must move closer to a base case.

The call stack stores one frame per active call. Deep recursion can exhaust the stack, which is why some recursive routines are rewritten as loops with an explicit stack.