Defining the Function in Terms of Itself
Recursion is when a function solves a problem by calling a smaller version of itself. It is not a trick or an advanced technique — it is a fundamental way of thinking about problems that have self-similar structure: trees, graphs, file systems, mathematical sequences.
Think of Russian nesting dolls (Matryoshka). To open the outermost doll, you open it and find a smaller doll inside. To open that one, you do the same thing. You keep going until you reach the smallest doll, which doesn't open — that's your base case.
The Two Laws of Recursion
Violate either law and you get a Stack Overflow (the program crashes because it runs out of memory).
Law 1 — The Base Case: A condition that returns a value without making another recursive call. This is the "stop" button.
Law 2 — The Recursive Step: Logic that calls the function again with a strictly smaller input, moving toward the base case.
def factorial(n):
if n == 0: # Law 1: Base Case — stop here
return 1
return n * factorial(n - 1) # Law 2: Recursive Step — smaller input (n-1)
The Call Stack
Every time a function calls itself, the computer pushes a new stack frame onto the Call Stack. This frame stores the local variables and the return address for that call. When the base case is reached, frames are popped off one by one as each call returns its result.
factorial(4)
→ factorial(3)
→ factorial(2)
→ factorial(1)
→ factorial(0) returns 1 ← base case
← returns 1 * 1 = 1
← returns 2 * 1 = 2
← returns 3 * 2 = 6
← returns 4 * 6 = 24
The depth limit: Python's default recursion limit is 1,000 frames. If your recursion goes deeper (e.g., a tree with 10,000 levels), you will hit a RecursionError. The fix is to either use an iterative approach (replace the call stack with an explicit stack data structure) or increase the limit with sys.setrecursionlimit() (use sparingly — it doesn't fix the underlying memory issue, it just delays the crash).