What is Recursion? How does it relate to the Call Stack?

Recursion is a technique where a function calls itself, directly or indirectly, to solve a problem by breaking it into smaller subproblems of the same type, until reaching a base case that can be solved without further recursion. Every recursive solution requires a base case (termination condition) and a recursive case that reduces the problem size.

Recursion relies on the call stack, a region of memory managed by the runtime that stores stack frames for each active function call. Each recursive call pushes a new frame onto the stack containing local variables, parameters, and the return address; when a call returns (typically hitting the base case), its frame is popped. This means the depth of recursion is bounded by the available stack memory.