Recursion

Recursion solves a problem by having a function call itself on smaller instances until it reaches a base case.

A function that calls itself

A recursive algorithm solves a problem in terms of smaller instances of the same problem. It has two parts: one or more base cases that are solved directly, and a recursive case that reduces the problem toward a base case and combines the sub-results. Correct recursion always makes progress toward a base case, or it never terminates.

The call stack

Each recursive call pushes a frame onto the call stack, holding that call's local state, and pops it when the call returns. The maximum depth of recursion therefore sets the stack memory used. Recursion that goes too deep overflows the stack, which is why deep recursions are sometimes rewritten as loops with an explicit stack.

• Base case: solved directly, stops the recursion
• Recursive case: reduces the problem and recombines
• Depth of recursion sets stack memory
• Any recursion can be made iterative with an explicit stack

def factorial(n):
    if n <= 1:        # base case
        return 1
    return n * factorial(n - 1)  # recursive case

Tail recursion

A recursive call is in tail position when it is the last action of the function, with nothing left to do after it returns. Some languages optimise tail calls into a loop that reuses one stack frame, avoiding overflow. Languages without that optimisation gain nothing, so the loop must be written by hand.

When recursion clarifies

Recursion is the natural expression of divide-and-conquer algorithms, tree and graph traversal, and problems defined by recurrences. It often yields shorter, clearer code than the iterative equivalent. When subproblems overlap, plain recursion repeats work, and memoization or dynamic programming is the cure.