Recursion

Base case + recursive case

Every recursion needs (1) a base case that returns without recursing, and (2) a recursive case that makes progress toward the base. Miss the base case and you get a stack overflow.

The call stack unwinds

factorial(3) waits for factorial(2) which waits for factorial(1). Then results multiply back up.

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

# factorial(3)
# = 3 * factorial(2)
# = 3 * (2 * factorial(1))
# = 3 * (2 * 1) = 6

Russian dolls

Open a doll to find a smaller one, until the tiny solid one (base case). Then close them back up in order.

Recursion → iteration

Any recursion can be rewritten with an explicit stack. Tail recursion and repeated subproblems (Fibonacci) are signals to memoise or go bottom-up.