What Makes a Method Recursive

A recursive method solves a problem by calling itself on a smaller piece of that same problem. For this to ever finish, the method needs a base case: a condition simple enough to answer directly, with no further calls. Every recursive call has to move toward that base case, usually by shrinking some parameter. Without a base case, or without progress toward it, the calls never stop and the program crashes with a stack overflow.

Each call to a recursive method gets its own copy of the parameters and local variables, stored in its own frame on the call stack. factorial(4) calls factorial(3), which calls factorial(2), which calls factorial(1), which calls factorial(0) and hits the base case, returning 1. That 1 travels back up: factorial(1) returns 1·1=1, factorial(2) returns 2·1=2, factorial(3) returns 3·2=6, factorial(4) returns 4·6=24. Nothing is overwritten along the way because each level keeps its own n and its own pending multiplication, waiting on the stack until the call below it returns.

This is what separates recursion from a loop dressed up to look fancy. A loop reuses one set of variables, updating them each pass. Recursion instead breaks the problem into a smaller version of itself and trusts that smaller version to solve itself, with its own fresh variables, until the base case bottoms out. That structure is exactly what makes recursion a natural fit for the searches, sorts, and tree-like traversals coming next in this unit, where splitting a problem into smaller copies of itself is the whole strategy.