What is recursion and how does it know when to stop

Recursion solves a problem by breaking it into smaller instances of the same problem. A recursive function contains two essential parts: the recursive step, which calls the function itself with a reduced argument, and the base case, which stops further calls. When the base case is reached, the function returns a value directly, and each previous call can combine that value to build the final answer.

The base case is a concrete condition that can be evaluated without another recursive call. It is usually expressed as an if‑statement that checks for the smallest possible input, such as zero, an empty list, or a single node. Once the condition is true, the function returns immediately, and the runtime system begins to unwind the call stack, replacing each pending call with its computed result.

The three ingredients that make recursion work:

• A clear base case
• A smaller‑problem recursive call
• Progress toward the base case

Tracing factorial(3) step by step:

1. 1factorial(3) calls factorial(2)
2. 2factorial(2) calls factorial(1)
3. 3factorial(1) meets base case and returns 1
4. 4Unwind: factorial(2)=21=2, factorial(3)=32=6

When a recursive call is made, the current execution context is pushed onto the call stack. Each frame stores the function’s parameters and local variables, waiting for the deeper call to finish. After the base case returns, the stack pops frames in reverse order, allowing each level to resume with the value it received.

Consider the classic factorial function defined as $\text{fact}(n) = 1$ if $n = 0$ else $n \times \text{fact}(n-1)$. Calling $\text{fact}(5)$ triggers the chain: $\text{fact}(5) \rightarrow \text{fact}(4) \rightarrow \text{fact}(3) \rightarrow \text{fact}(2) \rightarrow \text{fact}(1) \rightarrow \text{fact}(0)$. The base case $\text{fact}(0)=1$ returns 1, then each call multiplies the returned value by its own $n$, producing $1, 2, 6, 24,$ and finally $120$. This demonstrates how the base case halts recursion and the stack unwinds to give the final result.

Call stack frames for factorial(3):

Recursion is powerful because it mirrors the mathematical definition of many problems, but it must be used with care. Always verify that each recursive call moves the input closer to the base case, and test the function with the smallest inputs first. When these checks are in place, recursion will terminate reliably and produce the correct answer.