Recursion and the call stack

Recursion and the call stack

Half of what remains in this course — backtracking, DFS, dynamic programming, plus the merge sort you already met — is recursion wearing different clothes. Recursion exists because so much real data is self-similar: a directory contains directories, a JSON object contains objects, the left half of a list is itself a list. Code that processes such a structure most naturally calls itself on the smaller copies inside it — a plain loop has no clean way to descend and come back.

Recursion is a function calling itself on a smaller version of its own problem. Every correct recursive function has exactly two parts:

1. A base case: an input so small you return the answer directly. No self-call.
2. A recursive case: do a little work, then call yourself on something strictly closer to the base case.

Classic example: factorial(n) = n × (n-1) × ... × 1.

• Base case: factorial(1) is 1.
• Recursive case: factorial(n) is n * factorial(n - 1).

When a function calls itself, Python pauses the caller and remembers where it was. Those paused calls pile up on the call stack (the same stack data structure from Data Structures: last in, first out). Returns pop them off in reverse order.