Recursion and the Call Stack
Recursion is when a function solves a problem by calling itself on a smaller piece of the same problem. Every recursive solution needs two parts: a base case that stops the recursion, and a recursive case that moves toward that base.
The call stack
Each function call gets a stack frame holding its arguments and local variables. When a function calls itself, a new frame is pushed on top. When a call returns, its frame is popped and control resumes in the caller.
A recursion that forgets its base case keeps pushing frames until memory runs out, causing a stack overflow.
Thinking recursively
Trust that the recursive call correctly solves the smaller subproblem, then focus only on combining that result. For example, the factorial of a number is the number times the factorial of one less, stopping at one.
The maximum depth of recursion equals the tallest the stack ever grows, which matters for very deep inputs.
Key idea
Recursion pushes a stack frame per call and unwinds them on return, so a correct base case is essential.