Recursion

A smaller version of the same task

A recursive function calls itself on a smaller instance. It needs a base case that finishes without another call and a recursive step that moves toward that case. Before writing code, state what one function call promises to return or print.

Recursion is useful when a task naturally breaks into similar smaller tasks. It is not automatically faster than a loop. Each active call uses stack space, and repeating the same subproblem can make a short program very slow.

A complete example

The sum of the decimal digits of a nonnegative integer can be reduced by removing its last digit.

def digit_sum(n):
    if n < 10:
        return n
    return digit_sum(n // 10) + n % 10

print(digit_sum(472))

13

The call for 472 needs the result for 47, then adds 2. The call for 47 needs the result for 4, then adds 7. The call for 4 returns immediately. The returns combine in reverse order: 4, then 11, then 13.

Every recursive argument here is smaller. The base case handles zero as well as other single-digit values. Without a base case, calls continue until Python reports a recursion error.

Work before or after the call

Printing before the recursive call produces a different order from printing after it. A countdown prints n before calling the function for n - 1. An increasing sequence makes the smaller call first and prints n after it returns. Trace three calls by hand to see the difference.

Each call has its own local parameters. Global variables are shared between calls, which makes reasoning harder. An optional exercise explores that behavior after the ordinary recursive patterns.

Cost matters

A naive Fibonacci function calls both f(n - 1) and f(n - 2), repeating much work. It is acceptable only for small inputs. The later algorithm path teaches how to save subproblem results. Likewise, the Tower of Hanoi problem asks for the number of moves, not every move. Use the recurrence count(n) = 2 * count(n - 1) + 1. Simulating every move for 60 disks cannot finish.

Practice

The required sequence covers factorial, printing order, Fibonacci, a triangle, and a move-count recurrence. Optional extensions add a global state, Euclid's algorithm for least common multiple, base conversion, and combinations with repetition. Read their mathematical definitions before attempting them.

Check the smallest permitted input before a typical input. Then check that every branch either returns or makes progress toward a base case. If a recursive solution exceeds time or stack limits, changing the limit is not the first fix. Inspect repeated work and call depth.