Recursion

A function that calls itself

You have already seen one function call another:

def square(x: int) -> int:
    return x * x

def sum_of_squares(a: int, b: int) -> int:
    return square(a) + square(b)      # calls a different function

print(sum_of_squares(3, 4))

Now push that to its limit and let a function call itself:

def factorial(n: int) -> int:
    if n <= 1:
        return 1                       # bottom
    return n * factorial(n - 1)        # calls itself, with a smaller argument

print(factorial(5))

That is recursion, and it works because of one observation:

5 factorial = 5 × 4 factorial 4 factorial = 4 × 3 factorial … 1 factorial = 1 (no need to go further)

The problem “compute 5 factorial” has been turned into “compute 4 factorial” — a smaller problem of exactly the same kind. Keep shrinking until it is small enough to answer outright.

Mathematics has been defining things this way all along. The Fibonacci definition F(n) = F(n-1) + F(n-2) is recursive: it defines the thing in terms of itself.

Calling down, computing up

This is the step where recursion clicks, and also where people get lost. Calls go downward; computation comes back up.

Add some tracing to that factorial:

def factorial(n: int, depth: int = 0) -> int:
    pad = "  " * depth
    print(f"{pad}call factorial({n})")

    if n <= 1:
        print(f"{pad}bottom, return 1")
        return 1

    result = n * factorial(n - 1, depth + 1)

    print(f"{pad}factorial({n}) gives {result}")
    return result

factorial(5)

Look at the shape of the output: indenting all the way down (the calls), then unwinding all the way back up (the computation).

The line n * factorial(n - 1) is where it happens. To do that multiplication, Python must first know what factorial(n-1) is. So it waits. Only once the deepest call returns 1 can the level above compute 2 * 1, then the one above that 3 * 2, and so on.

The call stack

Every call requires Python to remember where it came from and what its local variables were. That information lives on the call stack.

A stack behaves like a pile of books: last on, first off. When factorial(5) calls factorial(4), the outer call has not finished — it sits underneath, waiting. Only when factorial(4) completes and is removed does factorial(5) continue.

call factorial(5)   →  stack: [f(5)]
call factorial(4)   →  stack: [f(5), f(4)]
call factorial(3)   →  stack: [f(5), f(4), f(3)]
call factorial(2)   →  stack: [f(5), f(4), f(3), f(2)]
call factorial(1)   →  stack: [f(5), f(4), f(3), f(2), f(1)]
f(1) returns 1      →  stack: [f(5), f(4), f(3), f(2)]
f(2) returns 2      →  stack: [f(5), f(4), f(3)]
...

The stack has a ceiling

Stack space is finite, and deep recursion runs into it:

import sys
print("Python's default recursion limit:", sys.getrecursionlimit())

def countdown(n: int) -> int:
    if n == 0:
        return 0
    return countdown(n - 1)

print(countdown(5000))

RecursionError means the stack filled up. It does not necessarily mean your algorithm is wrong — it means the recursion went deeper than Python allows.

The two ingredients

Every recursive function needs both of these:

One: a base case — a situation small enough to answer directly, with no further call.

Two: a recurrence — restating the problem as a smaller problem of the same kind.

def factorial(n: int) -> int:
    if n <= 1:          # ① base case
        return 1
    return n * factorial(n - 1)     # ② recurrence, and n-1 < n

The word smaller in point two is doing essential work. If the argument does not shrink, the base case is never reached:

def never_ends(n: int) -> int:
    if n == 0:
        return 0
    return never_ends(n)      # n did not get smaller
print(never_ends(3))

Some classics

Greatest common divisor

Euclid’s algorithm: gcd(a, b) = gcd(b, a % b), until b reaches 0.

def gcd(a: int, b: int) -> int:
    if b == 0:
        return a
    return gcd(b, a % b)

print(gcd(48, 18))
print(gcd(1071, 462))

One of the prettiest examples there is — three lines of code, twenty-three centuries old.

Fibonacci

def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print([fib(i) for i in range(10)])

The definition translates directly into code, almost implausibly neatly. But it hides something serious:

calls = 0

def fib(n: int) -> int:
    global calls
    calls += 1
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

for n in [10, 20, 25]:
    calls = 0
    fib(n)
    print(f"fib({n}) needs {calls} function calls")

fib(25) takes almost a quarter of a million calls, because fib(5) gets computed over and over — fib(7) needs it, fib(6) needs it, and both of those are demanded repeatedly from above.

The same subproblem is being recomputed an enormous number of times. The fix is to remember answers you have already worked out — memoization, which is L11’s business. For now, take away this: recursion is concise to write, and can conceal spectacular waste.

Fast exponentiation

Computing a to the n takes n multiplications the obvious way. Recursion gets it down to about log n:

def power(a: int, n: int) -> int:
    if n == 0:
        return 1
    half = power(a, n // 2)          # compute half of it
    if n % 2 == 0:
        return half * half
    return half * half * a

print(power(2, 10))
print(power(3, 5))
print(power(2, 100))

The idea: a^10 = (a^5)^2, and a^5 = (a^2)^2 × a. Each step halves the exponent, so log n steps suffice.

Note the line half = power(a, n // 2) — compute once, store it, use it twice. Written as power(a, n//2) * power(a, n//2) it would compute the same thing twice and throw away the entire advantage.

Divide and conquer

Fast exponentiation used divide and conquer: split the problem, solve the pieces, combine. Recursion is the natural way to express it.

Summing a nested list

A list may contain lists, to an unknown depth:

def deep_sum(items: list) -> int:
    total = 0
    for x in items:
        if isinstance(x, list):
            total += deep_sum(x)     # a list, so recurse into it
        else:
            total += x
    return total

print(deep_sum([1, [2, 3], [4, [5, [6, 7]]]]))

Writing this with loops is painful, because you do not know how many levels there are. Recursion handles structures of unknown depth for free.

Binary search

Finding a value in a sorted list. Compare against the middle and half the candidates disappear:

def binary_search(nums: list[int], target: int, lo: int = 0, hi: int | None = None) -> int:
    if hi is None:
        hi = len(nums) - 1
    if lo > hi:
        return -1                      # not present

    mid = (lo + hi) // 2
    if nums[mid] == target:
        return mid
    if nums[mid] < target:
        return binary_search(nums, target, mid + 1, hi)    # search the right half
    return binary_search(nums, target, lo, mid - 1)        # search the left half

data = [1, 3, 5, 7, 9, 11, 13, 15]
for t in [7, 1, 15, 8]:
    print(f"looking for {t} → index {binary_search(data, t)}")

Merge sort

Sorting by division: cut the list in half, sort each half, then merge two sorted lists.

def merge(a: list[int], b: list[int]) -> list[int]:
    """Merge two already-sorted lists."""
    result: list[int] = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    result.extend(a[i:])
    result.extend(b[j:])
    return result

def merge_sort(nums: list[int]) -> list[int]:
    if len(nums) <= 1:                 # base case: 0 or 1 items are already sorted
        return nums
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])      # sort the left half
    right = merge_sort(nums[mid:])     # sort the right half
    return merge(left, right)          # combine

print(merge_sort([7, 3, 4, 5, 1, 2, 3]))

merge_sort is exactly the two ingredients: the base case is “length at most 1”, the recurrence produces two half-length lists, and the size genuinely shrinks.

Towers of Hanoi: a shift in thinking

Every recursive function so far returned a value — factorial returns a number, binary search an index, merge sort a list.

Hanoi is different. What it returns is that something has been done.

The rules: three pegs, and n disks of different sizes stacked largest-at-the-bottom on the first peg. You may move one disk at a time, and a larger disk may never rest on a smaller one. Get all the disks onto the third peg.

Thinking about the moves directly will tie you in knots. Change the angle:

To move n disks from A to C, all you need is:

1. move the top n-1 disks from A to B (using C as the spare)
2. move the largest disk from A to C
3. move those n-1 disks from B to C (using A as the spare)

Steps 1 and 3 are the same problem again, one size smaller.

def hanoi(n: int, source: str, target: str, spare: str) -> None:
    """Move n disks from source to target, using spare as the intermediate peg."""
    if n == 1:
        print(f"  disk 1: {source} → {target}")
        return
    hanoi(n - 1, source, spare, target)          # ① the top n-1 to the spare peg
    print(f"  disk {n}: {source} → {target}")     # ② the largest goes straight across
    hanoi(n - 1, spare, target, source)          # ③ bring the n-1 back on top

print("three disks:")
hanoi(3, "A", "C", "B")

Count them: three disks take seven moves. You computed that number with a loop back in Lab 4: 2ⁿ - 1.

def count_moves(n: int) -> int:
    moves = 0
    def go(k: int) -> None:
        nonlocal moves
        moves += 1
        if k > 1:
            go(k - 1); go(k - 1)
    go(n)
    return moves

for n in range(1, 8):
    print(f"{n} disks: {count_moves(n)} moves (2^{n} - 1 = {2**n - 1})")

Generating every possibility

All permutations

Generate every ordering of a list. The idea: each position takes a turn holding each unused item.

def permutations(items: list[int]) -> list[list[int]]:
    if len(items) <= 1:
        return [items]                      # base case

    result: list[list[int]] = []
    for i in range(len(items)):
        rest = items[:i] + items[i + 1:]    # everything except item i
        for p in permutations(rest):        # every arrangement of the rest
            result.append([items[i]] + p)   # with item i in front
    return result

for p in permutations([1, 2, 3]):
    print(p)

The standard library has one built in, which makes a convenient check on your own version:

from itertools import permutations as std_perm

mine = [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
std = [list(p) for p in std_perm([1, 2, 3])]
print(sorted(mine) == sorted(std))

Eight queens

Place eight queens on an 8×8 board so that none attacks another — no shared row, column or diagonal.

Since every row holds exactly one queen, a solution fits in a single list: queens[i] = j means the queen in row i sits in column j.

def is_safe(queens: list[int], col: int) -> bool:
    """Does the new queen conflict with any already placed?"""
    row = len(queens)
    for r, c in enumerate(queens):
        if c == col:                        # same column
            return False
        if abs(row - r) == abs(col - c):    # same diagonal
            return False
    return True

def solve(n: int, queens: list[int] | None = None) -> int:
    if queens is None:
        queens = []
    if len(queens) == n:
        return 1                            # the board is full: one solution
    count = 0
    for col in range(n):
        if is_safe(queens, col):
            count += solve(n, queens + [col])   # place it, then carry on
    return count

for n in range(4, 9):
    print(f"{n} queens: {solve(n)} solutions")

The technique is called backtracking: try a move, and when it leads nowhere, back up and try another. It is recursion at heart — solve is responsible for counting every complete solution that extends the partial one it was given.

A fractal you can actually run

A fractal contains scaled-down copies of itself, which makes it a natural fit for recursion. The Sierpinski triangle draws perfectly well in text:

def sierpinski(n: int) -> list[str]:
    """Return the Sierpinski triangle as 2^n lines of text."""
    if n == 0:
        return ["*"]

    smaller = sierpinski(n - 1)
    size = len(smaller)
    pad = " " * size
    # top half: one small triangle, centered; bottom half: two side by side
    top = [pad + line + pad for line in smaller]
    bottom = [line + " " + line for line in smaller]
    return top + bottom

for line in sierpinski(4):
    print(line)

Change the number in sierpinski(4) and run it again — each increment doubles the size of the figure, without a single change to the code.

Recursion or a loop?

Anything recursive can be rewritten as a loop, and vice versa. So when is each the right choice?

# factorial: the loop is more direct and cheaper
def factorial_loop(n: int) -> int:
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

def factorial_rec(n: int) -> int:
    return 1 if n <= 1 else n * factorial_rec(n - 1)

print(factorial_loop(10), factorial_rec(10))

For linear problems like factorials and running totals, a loop fits better — you can state plainly how things change from i to i+1.

But for Hanoi, eight queens, or walking a nested structure, a loop is agony, because you end up maintaining your own stack to simulate what recursion does for free.

Summary

• Recursion restates a problem as a smaller problem of the same kind, until it is small enough to answer outright
• Calls go down; computation comes back up
• Two required ingredients: a base case, and a recurrence that genuinely shrinks. Missing either gives RecursionError
• Every level occupies call stack space; Python allows roughly 1000 by default
• Take the leap of faith: assume the next level down does its job correctly
• Naive fib recomputes the same subproblem hundreds of thousands of times — L11 fixes it
• Divide and conquer: binary search and merge sort both split, solve, and recombine
• Hanoi-style recursion returns no value; it returns the fact that a task is done — that is the conceptual threshold
• Backtracking: try, and back up when it fails
• Use recursion when the problem’s structure is recursive; use a loop when it is linear

Exercises

1. Write count_digits(n: int) -> int counting the digits of a non-negative integer recursively. Think carefully about the base case for n = 0.
2. Write reverse_string(s: str) -> str recursively. Slicing with [::-1] is not allowed.
3. Write sum_digits(n: int) -> int recursively, and compare it with the loop version you wrote for Lab 4.
4. Add a counter to fib and chart the number of calls for n from 1 to 25. What kind of growth does it look like to you?
5. Write flatten(items: list) -> list[int], flattening a list nested to any depth. For instance [1, [2, [3, [4]]]] → [1, 2, 3, 4].
6. Modify this lecture’s hanoi() so it returns the list of moves rather than printing them. Then consider: is it still “accomplish a task” recursion?
7. Implement is_palindrome(s: str) -> bool recursively, testing whether a string reads the same in both directions.

The lab problems are in Lab 7, and solo project A opens this week.