Recursion is when a function solves a problem by calling itself on a smaller instance of the same problem. Every correct recursion has two ingredients: one or more base cases that are solved directly without further recursion, and a recursive case that reduces the problem toward a base case. Omit the base case and you get infinite recursion; fail to make progress toward it and the same.

Recursion is powered by the call stack: each call gets its own stack frame holding its local variables and its return address. Calls stack up as the recursion descends and unwind — in strict LIFO order — as each returns. This is the same stack structure from Chapter 5, now doing the language's own bookkeeping.

Many powerful techniques are inherently recursive: divide and conquer (merge sort), tree and graph traversal, and problems with self-similar structure. A recurrence like T(n) = 2·T(n/2) + O(n) captures such costs and, by the Master Theorem, resolves to O(n log n).

The trick to trusting recursion is the leap of faith: assume the function already works correctly for smaller inputs, then only make sure you (a) handle the base case and (b) combine the smaller solution correctly. If both hold, induction guarantees the whole thing is right. You do not — and should not — trace every level in your head.

Recursion and iteration are equally powerful; anything one can do, so can the other. The choice is about clarity. Tree-shaped problems read beautifully as recursion and painfully as loops-with-explicit-stacks. But recursion has a cost: each pending call consumes a stack frame, so very deep recursion can overflow the stack — where a loop would use constant space.

Three classics: factorial (linear recursion), Fibonacci (tree recursion, with a memoised fix), and the Tower of Hanoi (exponential but elegant).

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

def fib(n):                 # naive: O(2^n) -- recomputes the same values
    if n < 2:
        return n            # base cases: fib(0)=0, fib(1)=1
    return fib(n - 1) + fib(n - 2)

def fib_fast(n, memo=None):              # memoised: O(n)
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib_fast(n - 1, memo) + fib_fast(n - 2, memo)   # cache result
    return memo[n]

def hanoi(n, source, target, spare):
    """Move n disks from source to target using spare, printing each move."""
    if n == 0:
        return                           # base case: nothing to move
    hanoi(n - 1, source, spare, target)  # move top n-1 out of the way
    print("move disk " + str(n) + ": " + source + " -> " + target)
    hanoi(n - 1, spare, target, source)  # move them onto the target

print(factorial(5))     # 120
print(fib_fast(30))     # 832040  (instant; naive fib(30) does ~2.7M calls)
hanoi(3, "A", "C", "B") # 7 moves = 2^3 - 1

Naive fib is a cautionary tale: it recomputes fib(2) exponentially many times. Memoisation — caching each answer the first time — collapses it from O(2ⁿ) to O(n). Hanoi shows the opposite: 2ⁿ−1 moves is optimal, an inherently exponential task expressed in four tidy lines.