Recursion

I. Calls and recursive functions

A caller resumes after a return

Lists can contain other lists. Last lecture’s containers allow a structure such as [1, [2, 3], [4, [5]]], where the depth varies between elements. Two fixed loops cannot cover every possible nesting depth. Could the function that processes the outer list also process an inner list?

First, recall what happens when one function calls another. Predict the output before running this example.

def inner() -> int:
    print("B")
    return 2

def outer() -> int:
    print("A")
    result = inner()
    print("C")
    return result + 1

print(outer())

The four lines are A, B, C, and 3. Calling inner does not end the call to outer. The caller keeps its local state and resumes at the next operation once the callee returns.

The called name must be bound to a function when execution reaches the call. Its definition need not always appear earlier than the caller’s definition in the source file. Both names above are bound before outer() runs.

Factorial as a recursive definition

A function uses recursion when it calls itself, either directly or through other functions. Factorial provides a small numerical example:

• 0! = 1;
• for positive integers, n! = n × (n−1)!.

The following function accepts a nonnegative integer. The annotation n: int documents a type; it does not enforce that type or reject negative values at runtime.

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

print(factorial(3))
print([factorial(n) for n in range(6)])

The results are 6 and [1, 1, 2, 6, 24, 120]. Each recursive call reduces n by one. At zero, the function returns an answer without making another call.

Tracing calls and returns

This implementation cannot finish its multiplication until the smaller factorial returns. The extra parameter below controls indentation, not the mathematical result.

def factorial(n: int, depth: int = 0) -> int:
    pad = "  " * depth
    print(f"{pad}enter {n}")
    if n == 0:
        result = 1
    else:
        result = n * factorial(n - 1, depth + 1)
    print(f"{pad}return {result}")
    return result

print(factorial(3))

Calls enter with 3 → 2 → 1 → 0. The four returning values are 1 → 1 → 2 → 6. Finally, the outer print writes 6.

Each call has a separate local environment. Binding n to 1 in an inner call does not change the outer call’s n = 2. When factorial(2) resumes, it multiplies its own 2 by the returned 1.

Here, multiplication happens after the recursive call. That is a property of this factorial implementation, not a rule for all recursion. Work can happen before a call, after a call, or between two calls. Hanoi will demonstrate the last case.

The call stack and recursion limits

An unfinished call needs local state and a place to resume execution. A call stack describes these outstanding calls. Its order is LIFO, last in, first out: an inner call completes before its waiting caller continues.

enter f(3)       [f(3)]
enter f(2)       [f(3), f(2)]
enter f(1)       [f(3), f(2), f(1)]
enter f(0)       [f(3), f(2), f(1), f(0)]
f(0) returns 1  [f(3), f(2), f(1)]
f(1) returns 1  [f(3), f(2)]
f(2) returns 2  [f(3)]
f(3) returns 6  []

These are logical call frames, not a diagram of CPython’s physical memory layout. Calls require execution state, but interpreters can represent that state differently.

import sys

print("Recursion limit:", sys.getrecursionlimit())

A common limit is 1000; use the actual output for the current environment. Existing calls also consume depth, so this number does not promise that the thousandth call made by the student program will be the first to fail.

The next function terminates mathematically, yet its chain is too deep for the default limit used in this lecture’s checks. Running it is intended to raise RecursionError.

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

print(countdown(5000))

A RecursionError means the interpreter’s allowed recursion depth was exceeded. It does not show that physical memory has been exhausted. A nonterminating algorithm and a terminating algorithm with a very deep input can both produce this exception. Raising the limit is not the remedy taught here.

Base cases and progress

For termination over the promised input domain, identify three things:

1. A base case that makes no further recursive call.
2. A recursive step defining the smaller task and how its result is used.
3. A progress argument showing that recursion reaches a base case. A strictly decreasing nonnegative integer measure suffices for the main examples.

The measure might be n, a list’s length, or the number of rows still unfilled. Not every parameter has to decrease numerically. Queens search places more queens while leaving fewer rows to fill. The reference Ackermann example instead needs a layered comparison of two arguments.

The next three blocks demonstrate different failures. Each intentionally raises RecursionError under the default limit.

No base case.

def bad(n: int) -> int:
    return n * bad(n - 1)

print(bad(3))

A base case exists, but the recursive call makes no progress.

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

print(never_ends(3))

The argument decreases but skips the base case.

def down(n: int) -> int:
    if n == 0:
        return 0
    return down(n - 2)

print(down(3))

The last sequence is 3, 1, -1, -3, .... It never reaches zero. “The number gets smaller” is not a complete termination argument.

For correctness, state the function’s contract, check the base case, assume that the smaller task is solved correctly, and show that the current step produces the required answer. This induction-style reasoning also needs termination. A correct-looking formula for one step is not sufficient by itself.

II. Recursive data and subproblems

Checking types with isinstance

isinstance(x, list) returns a Boolean indicating whether x is a list instance. It also accepts instances of list subclasses; the examples here use ordinary lists.

for x in [3, [1, 2], []]:
    print(isinstance(x, list))

The results are False, True, and True. This test lets the next function distinguish integer elements from inner lists.

Its contract is a finite nested list with no cycles, whose non-list elements are integers. A list containing itself has a cycle and is outside this domain.

def deep_sum(items: list) -> int:
    total = 0
    for x in items:
        if isinstance(x, list):
            total += deep_sum(x)
        else:
            total += x
    return total

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

The answers are 28, 3, and 0. Every call has its own total. On an empty list, the loop runs zero times and returns the initial zero; a separate if is unnecessary.

The loop handles siblings at one level, while recursive calls handle inner lists. No fixed nesting depth appears in the code, but real depth and storage limits still apply. An explicit-stack implementation appears in the reference section.

Euclid’s algorithm

For nonnegative integers a and b, Euclid’s algorithm uses:

• gcd(a, 0) = a;
• if b > 0, gcd(a, b) = gcd(b, a % b).

The usual mathematical domain excludes the pair (0, 0). This implementation additionally adopts the convention that gcd(0, 0) returns zero.

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))
print(gcd(0, 5))

The outputs are 6, 21, and 5. For the first example, the pairs are (48, 18) → (18, 12) → (12, 6) → (6, 0). With b > 0, the remainder is nonnegative and strictly smaller than b. The second parameter is the decreasing measure even when the first parameter increases.

Fibonacci and repeated work

Use F(0) = 0, F(1) = 1, and F(n) = F(n−1) + F(n−2) for n ≥ 2. The input is a nonnegative integer.

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

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

The sequence starts [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]. Each non-base call makes two child calls. The call tree for fib(5) contains two separate calls to fib(3). Python does not automatically reuse an answer just because the argument is the same.

Return both the value and the number of calls to measure this work. A base call counts as one; any other call counts itself plus both child trees.

def fib_counted(n: int) -> tuple[int, int]:
    if n <= 1:
        return n, 1
    left, c1 = fib_counted(n - 1)
    right, c2 = fib_counted(n - 2)
    return left + right, 1 + c1 + c2

for n in [5, 10, 20, 25]:
    value, calls = fib_counted(n)
    print(n, value, calls)

The call counts for 5, 10, 20, 25 are 15, 177, 21891, 242785. These are exact counts including base calls, not 2ⁿ calls and not timings in seconds.

The main problem is repeated computation. Saving answers for reuse is called memoization, a later topic. For now, compare the two iterative implementations in the reference section.

Fast exponentiation

Let a be an integer and n a nonnegative integer exponent:

• a⁰ = 1; the implementation uses this convention for power(0, 0) too;
• for even n, aⁿ = (a^(n//2))²;
• for odd n, multiply that square by one more a.

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

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

The values are 1024, 243, and 1267650600228229401496703205376. The exponent chain 10 → 5 → 2 → 1 → 0 makes just one smaller recursive call at each level. half holds its result and supplies both factors of the square.

Writing power(a, n // 2) twice would make two calls. Equal arguments do not imply automatic result caching.

Starting with one and multiplying by a repeatedly takes n multiplications. Fast exponentiation halves the exponent and uses one or two multiplications per non-base call. Its arithmetic-operation count grows with the number of bits in the exponent. However, intermediate integers get larger, so their multiplication and storage costs are not constant. A logarithmic count of multiplications is not a claim of logarithmic total time for arbitrarily large integers. The reference example counts operations explicitly.

III. Divide and conquer

Divide and conquer solves a problem through smaller subproblems and uses their results. Binary search keeps one candidate subrange. Merge sort sorts two sublists and merges them. Fast exponentiation solves one subproblem and reuses its result. These structures do not require the same amount of work.

Binary search needs sorted input

The input must already be sorted in nondecreasing order. Only then does a comparison with the middle justify discarding one side. This implementation neither sorts the input nor checks that it is sorted.

Use an inclusive range [lo, hi]. It is empty when lo > hi. The helper searches that range; the public wrapper supplies the full-list bounds.

def search_range(nums: list[int], target: int,
                 lo: int, hi: int) -> int:
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if nums[mid] == target:
        return mid
    if nums[mid] < target:
        return search_range(nums, target, mid + 1, hi)
    return search_range(nums, target, lo, mid - 1)

def binary_search(nums: list[int], target: int) -> int:
    return search_range(nums, target, 0, len(nums) - 1)

data = [1, 3, 5, 7, 9, 11, 13, 15]
for target in [7, 1, 15, 8]:
    print(target, binary_search(data, target))
print("empty:", binary_search([], 3))
print("single hit:", binary_search([3], 3))
print("single miss:", binary_search([3], 4))
print("duplicates:", binary_search([1, 3, 3, 3, 5], 3))

Searching for 15 visits [0,7] → [4,7] → [6,7] → [7,7]. Searching for 8 visits [0,7] → [4,7] → [4,4] → [4,3] and returns -1.

The already-tested midpoint must be excluded: use mid + 1 or mid - 1. The tests cover empty input, a singleton, and a missing value. With duplicates, the function returns any matching index, not necessarily the leftmost one.

A million elements require at most about twenty midpoint examinations. This is not exactly twenty executions of == or <; a round can perform two value comparisons. L11 develops the formal complexity analysis.

Merge sort and the merge operation

Split the list, sort both halves, then merge the sorted results. A list of length zero or one needs no rearrangement.

During merging, i and j point to the first unused elements. Append the smaller one; once a side is exhausted, append everything left on the other side. The runnable block includes the helper as well as the recursive function.

def merge(a: list[int], b: list[int]) -> list[int]:
    result: list[int] = []
    i = 0
    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:
        return nums.copy()
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    return merge(left, right)

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

The sorted result is [1, 2, 3, 3, 4, 5, 7]. Duplicate values remain, and the input is unchanged. Even the base case returns a copy, so the result is always a new list.

Both recursive lists are shorter than the original. That establishes progress. Merging, slicing, and allocating lists still require work and storage; counting recursion levels alone would miss those costs.

IV. Hanoi instructions

Rules and decomposition

Three pegs are named A, B, and C. Initially, n different-sized disks are on A, with larger disks below smaller ones. Disk numbers run from 1 to n; larger numbers mean larger disks. A move takes one top disk to another peg, never placing a larger disk on a smaller one. The goal is to transfer the stack to C.

The function here prints instructions. It does not store or mutate the pegs. Its inputs are a nonnegative n and three distinct peg names. A transfer from source to target using spare has three stages:

1. Transfer the top n−1 disks from source to spare, using target.
2. Transfer disk n from source to target.
3. Transfer the n−1 disks from spare to target, using source.

Peg names stay the same; their roles change between tasks. Zero disks require no instructions.

def hanoi(n: int, source: str, target: str, spare: str) -> None:
    if n == 0:
        return
    hanoi(n - 1, source, spare, target)
    print(f"disk {n}: {source} -> {target}")
    hanoi(n - 1, spare, target, source)

hanoi(3, "A", "C", "B")

There are seven printed instructions. The print lies between the two recursive calls, establishing the required order. To validate an actual sequence, a separate checker must track pegs, confirm that each moved disk is on top, enforce the size rule, and check the final position. Printing text does not perform those state changes.

Move counts and the minimum

Let T(n) be the minimum number of moves for ordinary three-peg Hanoi. Before the largest disk first leaves the source, all smaller disks must be on the other available peg. After it finally reaches the target, the smaller stack must join it. Considering the largest disk’s route gives a lower bound of two transfers of n−1 disks and one largest-disk move; routing the largest disk through the spare peg requires more work, not less.

The three-stage construction achieves that bound. Thus T(0) = 0, T(n) = 2T(n−1) + 1, and T(n) = 2ⁿ−1. Count moves with a returned result rather than a shared counter.

def count_moves(n: int) -> int:
    if n == 0:
        return 0
    smaller = count_moves(n - 1)
    return 2 * smaller + 1

for n in range(8):
    print(n, count_moves(n), 2**n - 1)

This is a move count, not a count of calls to hanoi. The three-disk instruction printer makes fifteen calls including its zero-disk calls. Its depth grows with n, while the number of output instructions grows exponentially.

Output is not a return value

The annotation -> None does not prevent a function from returning. A bare return, or reaching the end of a function, returns the value None. This example prints an instruction and then prints the returned value.

def hanoi(n: int, source: str, target: str, spare: str) -> None:
    if n == 0:
        return
    hanoi(n - 1, source, spare, target)
    print(f"disk {n}: {source} -> {target}")
    hanoi(n - 1, spare, target, source)

result = hanoi(1, "A", "C", "B")
print(result)

Its effect is printed text; its return value is None. Computing a value, producing output, and changing state are distinct contracts. An exercise asks for an instruction list instead. The solo assignment also requires sequence validation: matching a move-count formula alone is not enough.

V. Enumeration and backtracking

Full permutations, including the empty one

A permutation is an ordering of all the list’s elements. Define the recursive task as “return all orderings of the remaining elements.” Choose a first element, permute the rest, and prepend the chosen element to each result.

def permutations(items: list[int]) -> list[list[int]]:
    if len(items) <= 1:
        return [items.copy()]
    result: list[list[int]] = []
    for i in range(len(items)):
        rest = items[:i] + items[i + 1:]
        for p in permutations(rest):
            result.append([items[i]] + p)
    return result

for p in permutations([1, 2, 3]):
    print(p)
print("empty:", permutations([]))
print("single:", permutations([7]))
print("duplicates:", permutations([1, 1, 2]))

An empty input returns [[]]: there is one empty ordering, not zero orderings. Copying the base-case list avoids sharing a mutable result list with the input.

Elements are selected by position. Consequently, [1, 1, 2] produces six entries but only three distinct value sequences. The function does not deduplicate or modify its input.

Checking against the standard library

itertools.permutations is useful for small-input checks. It yields tuples, converted to lists here. The check must actually call the implementation under test. Sorting lists of results preserves multiplicities; comparing sets would erase them.

from itertools import permutations as std_perm

def permutations(items: list[int]) -> list[list[int]]:
    if len(items) <= 1:
        return [items.copy()]
    result: list[list[int]] = []
    for i in range(len(items)):
        rest = items[:i] + items[i + 1:]
        for p in permutations(rest):
            result.append([items[i]] + p)
    return result

for items in [[], [7], [1, 2, 3], [1, 1, 2]]:
    mine = permutations(items)
    standard = [list(p) for p in std_perm(items)]
    print(items, len(mine), len(standard), sorted(mine) == sorted(standard))

All four comparisons are True, with counts 1, 1, 6, and 6. These tests cover useful boundaries, but a finite test set is not a general proof.

Queens as a partial solution

Place n queens on an n × n board without a shared row, column, or diagonal. Placing one queen per row enforces the row constraint by construction. Store a partial solution as queens[row] = column, using zero-based indices. For example, [1, 3, 0, 2] solves the four-queens problem.

The next row is len(queens). A new column col conflicts with an earlier queen (r, c) if col == c, or if abs(row - r) == abs(col - c) for a diagonal.

def is_safe(queens: list[int], col: int) -> bool:
    row = len(queens)
    for r, c in enumerate(queens):
        if c == col:
            return False
        if abs(row - r) == abs(col - c):
            return False
    return True

def count_queens(n: int, queens: list[int]) -> int:
    if len(queens) == n:
        return 1
    total = 0
    for col in range(n):
        if is_safe(queens, col):
            total += count_queens(n, queens + [col])
    return total

for n in range(4, 9):
    print(n, count_queens(n, []))

The counts are 2, 10, 4, 40, and 92. Pass the initial partial solution [] explicitly. Recursive calls receive only legal partial solutions, and the number of unfilled rows, n - len(queens), decreases.

Backtracking tries candidate extensions and abandons conflicting branches before exploring them further. Here, queens + [col] creates a new list; the caller’s partial solution is unchanged, so no mutation needs undoing. An implementation using append on one shared list would need a corresponding undo after returning. The reference section also presents the older method of generating every column permutation and then checking diagonals.

A self-similar figure

A Sierpinski triangle consists of three smaller copies arranged into the next level. That exact self-similarity makes a recursive construction convenient. Not every fractal must consist of exactly identical reduced copies.

The text implementation below takes a nonnegative level n and returns 2ⁿ strings.

def sierpinski(n: int) -> list[str]:
    if n == 0:
        return ["*"]
    smaller = sierpinski(n - 1)
    size = len(smaller)
    pad = " " * size
    top = [pad + line + pad for line in smaller]
    bottom = [line + " " + line for line in smaller]
    return top + bottom

for line in sierpinski(3):
    print(line)
for n in range(5):
    lines = sierpinski(n)
    stars = 0
    for line in lines:
        stars += line.count("*")
    print(n, len(lines), stars)

One copy forms the top half; two form the bottom half. Each increase of n doubles the line count and triples the star count. For n = 0..4, these are 1, 2, 4, 8, 16 lines and 1, 3, 9, 27, 81 stars. The text width includes formatting spaces, so it should not be identified directly with a geometric side length.

VI. Choosing recursion or iteration

A recursive algorithm can be expressed as a loop with explicit state. That may require a stack or another container for pending work; replacing a call with a for is not a general recipe.

Factorial is useful for learning the mechanism, although a loop is usually a more direct implementation. Both versions below accept nonnegative integers.

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:
    if n == 0:
        return 1
    return n * factorial_rec(n - 1)

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

Both return 3628800 and perform comparable numbers of multiplications. The recursive version additionally keeps outstanding calls. In contrast, naive recursive Fibonacci differs from iterative Fibonacci mainly because it repeats subproblems, not merely because one function call has overhead.

Compare problem structure, repeated work, maximum depth, copying, and output size. Shorter code is not evidence of a faster or correct algorithm.

Summary

• A recursive contract includes its input domain, base case, recursive step, and termination argument.
• Each call has separate local bindings; callers resume after callees return.
• Work can occur before, after, or between recursive calls.
• RecursionError reports a depth limit, not proof of physical memory exhaustion.
• Nested traversal, binary search, merge sort, and power have different subproblem structures.
• Naive Fibonacci repeats work; retaining a returned result can prevent a repeated call.
• The Hanoi example prints instructions and returns None; it does not mutate pegs.
• Backtracking extends legal partial solutions and cuts off conflicting branches.
• Recursion and iteration both consume time and storage. Compare actual implementations.

Practice exercises

The seven exercises remain part of the lecture. Implement tasks shared with Lab 7 independently; the reference examples illustrate related ideas rather than supplying complete lab submissions.

1. Write count_digits(n: int) -> int to count decimal digits recursively for nonnegative integers. Explain the base case for zero.
2. Write reverse_string(s: str) -> str recursively without [::-1]. Test the empty string and a single character.
3. Write sum_digits(n: int) -> int recursively for nonnegative integers. Compare it with the loop from Lab 4, including zero and inputs whose digit count exceeds the available recursive depth.
4. Count calls to fib for n = 1..25 using explicit parameters or returned counts. Plot the growth and explain repeated subproblems.
5. Write flatten(items: list) -> list[int] for finite acyclic nested lists with integer leaves. Preserve left-to-right order without modifying the input. For example, [1, [2, [3, [4]]]] becomes [1, 2, 3, 4]. Test empty lists at both outer and inner levels.
6. Change hanoi to return a list of move instructions instead of printing. Distinguish returning a plan from executing moves and validating states.
7. Implement recursive is_palindrome(s: str) -> bool. State the results for an empty string and a single character.

See Lab 7 for the accompanying practice. Solo assignment 1 concerns ordinary Hanoi and the adjacent-peg variant, including sequence construction and verification. This lecture does not supply a complete assignment solution; consult the formal assignment for submission rules, grading, and dates.

Reference: implementations and extensions

These examples are for further study. Every runnable block supplies its own dependencies; none relies on another block having run first.

Traversing with an explicit stack

Keep pending elements in a list and remove the last element with pop(). This gives a loop version of nested summation. The same finite, acyclic, integer-leaf input contract applies.

def deep_sum_stack(items: list) -> int:
    pending = items.copy()
    total = 0
    while pending:
        x = pending.pop()
        if isinstance(x, list):
            pending.extend(x)
        else:
            total += x
    return total

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

Last elements are processed first, unlike the main example’s left-to-right traversal. Order does not change an integer sum, but it matters when producing an ordered flattened list. An explicit stack avoids a recursive call chain, not storage costs.

Counting power operations

Return the value and the multiplication count. The even branch adds one multiplication and the odd branch adds two, including trivial products such as 1 * 1.

def power_counted(a: int, n: int) -> tuple[int, int]:
    if n == 0:
        return 1, 0
    half, multiplications = power_counted(a, n // 2)
    if n % 2 == 0:
        return half * half, multiplications + 1
    return half * half * a, multiplications + 2

for n in [0, 1, 5, 10, 100]:
    value, multiplications = power_counted(2, n)
    print(n, value, multiplications)

For power_counted(2, 10), the exponent chain is 10, 5, 2, 1, 0, with six multiplications. Depth, operation count, and result size are separate measures. A very large result needs space even if few operations produced it, and multiplying large integers costs more than multiplying small ones.

Numeric recursion: binary representation

For a nonnegative integer, division by two gives a smaller quotient and the lowest binary digit as the remainder. Append that remainder to the quotient’s representation. Zero is represented by "0" without a further call.

def binary_text(n: int) -> str:
    if n < 2:
        return str(n)
    return binary_text(n // 2) + str(n % 2)

for n in [0, 1, 2, 13]:
    print(n, binary_text(n))

A binary string’s length is different from the number of ones it contains. The latter is the set-bit count, with zero contributing no set bits.

def count_set_bits(n: int) -> int:
    if n == 0:
        return 0
    return count_set_bits(n // 2) + n % 2

for n in [0, 1, 2, 13]:
    print(n, count_set_bits(n))

Decimal digits and integer reversal

In base ten, n // 10 removes the last digit and n % 10 extracts it. A single decimal digit, including zero, has length one. The digit-count exercise must distinguish zero as an original input from a recursion’s stopping state; its complete implementation is left to the student.

This separate example reverses a nonnegative integer, using string length to locate the last digit in the result. It does not implement the string-reversal exercise.

def reverse_decimal(n: int) -> int:
    if n < 10:
        return n
    width = len(str(n))
    return (n % 10) * 10**(width - 1) + reverse_decimal(n // 10)

for n in [0, 7, 120, 1000, 2026]:
    print(n, len(str(n)), reverse_decimal(n))

Reversing 120 as an integer gives 21: leading zeros cannot be retained in an integer value. Each level converts a shorter prefix to a string again. Recomputing the width recursively at every level would also repeat work. This approach is not automatically preferable to a loop.

Three approaches to digit sums

A digit sum can use a string loop, an arithmetic while, or recursive decomposition. To keep Lab 7-5 an implementation exercise, this block demonstrates the two loops and the recursive digit contributions only for 2026. It does not provide a general recursive digit-sum function.

n = 2026

text_total = 0
for digit in str(n):
    text_total += int(digit)

arithmetic_total = 0
remaining = n
while remaining > 0:
    arithmetic_total += remaining % 10
    remaining //= 10

def trace_digit_contributions(prefix: int) -> None:
    print("prefix and last digit:", prefix, prefix % 10)
    if prefix >= 10:
        trace_digit_contributions(prefix // 10)

trace_digit_contributions(n)
expanded_total = 6 + (2 + (0 + 2))
print(text_total, arithmetic_total, expanded_total)

All three numerical results are 10. The tracing function prints prefixes and last digits and returns None. expanded_total is the expansion for this one input, not a reusable summation function. In the exercise, supply the return-value combination, the base case, and the behavior for zero yourself.

10**1000 has 1001 decimal digits: a one followed by a thousand zeros. Finite inputs can still require more recursive depth than the interpreter permits.

import sys

n = 10**1000
print("Decimal digits:", len(str(n)))
print("Recursion limit:", sys.getrecursionlimit())

This conversion is within the usual limit on integer-to-decimal-string conversion. Do not infer that converting arbitrarily large integers with str has no separate limit. Record the actual exception produced by a digit recursion in its environment rather than raising limits and claiming universal support.

A third-order recurrence

The older material uses this recurrence, not the sum of three preceding terms:

a₁ = 1, a₂ = 2, a₃ = 3;

aₙ₊₃ = 3aₙ₊₂ − 2aₙ₊₁ + aₙ, for n ≥ 1.

Here k is a positive integer term index. Each initial value has a corresponding base case.

def third_order(k: int) -> int:
    if k == 1:
        return 1
    if k == 2:
        return 2
    if k == 3:
        return 3
    return (3 * third_order(k - 1)
            - 2 * third_order(k - 2)
            + third_order(k - 3))

print([third_order(k) for k in range(1, 9)])

The first eight terms are [1, 2, 3, 6, 14, 33, 77, 179]. This direct version also repeats subproblems; the example deliberately uses small indices.

Repairing a two-dimensional boundary

The old boundaries f(0, n) = 1 and f(m, 0) = m give conflicting values at (0, 0): one and zero. This lecture explicitly revises the second boundary’s domain:

• f(0, n) = 1 for n ≥ 0;
• f(m, 0) = m for m ≥ 1;
• f(m, n) = f(m−1, n) + f(m, n−1) − f(m−1, n−1) for m, n ≥ 1.

Thus f(0, 0) = 1. This is a stated choice of a consistent version, not a claim that the original statement was unambiguous. Both inputs are nonnegative integers.

def grid_value(m: int, n: int) -> int:
    if m == 0:
        return 1
    if n == 0:
        return m
    return (grid_value(m - 1, n)
            + grid_value(m, n - 1)
            - grid_value(m - 1, n - 1))

for m in range(5):
    print([grid_value(m, n) for n in range(5)])

Checking m == 0 first handles the origin correctly. The five rows are constant rows of 1, 1, 2, 3, and 4. Every child call has a smaller m + n.

Small Ackermann inputs

For nonnegative integers, the Ackermann function is defined by:

• A(0, n) = n + 1;
• A(m+1, 0) = A(m, 1);
• A(m+1, n+1) = A(m, A(m+1, n)).

The last rule evaluates an inner call before using its answer as an outer argument. A claim that every numerical argument decreases would be false.

def ackermann(m: int, n: int) -> int:
    if m == 0:
        return n + 1
    if n == 0:
        return ackermann(m - 1, 1)
    return ackermann(m - 1, ackermann(m, n - 1))

for m, n in [(0, 1), (1, 1), (2, 2)]:
    print(m, n, ackermann(m, n))

The answers are 2, 3, and 7. Termination can be argued in layers: with the larger first argument fixed, the inner call lowers the second; after lowering the first argument, calls can accept larger second arguments. Mathematical termination does not guarantee that a real interpreter can support the depth.

The function grows extremely quickly. Do not recursively evaluate huge examples such as A(4, 2) here, and do not raise the recursion limit. The formula A(4, 2) = 2**65536 - 3 describes a result; stating it is not evidence of having completed the recursive computation.

Local turtle drawing: a recursive star

turtle supplies a drawing window and a pen. forward(size) moves along the current heading, left(angle) turns left, and position() and heading() report the pen’s state. The example requires a local graphical environment and intentionally has no browser Run button.

import turtle

def star(pen, size: float) -> None:
    if size <= 10:
        return
    for _ in range(5):
        pen.forward(size)
        star(pen, size / 3)
        pen.left(216)

screen = turtle.Screen()
pen = turtle.Turtle()
pen.speed(0)
star(pen, 360)
screen.exitonclick()

This is the older lecture’s recursive five-pointed star, not a recursive tree. Each edge is followed by a smaller star at the current position. Five turns of 216° total 1080°, restoring the heading; a complete child drawing also restores its position and heading.

For size 360, the drawing levels have sizes 360, 120, 40, and 40/3; the next level stops. There are 5 + 25 + 125 + 625 = 780 line segments and 781 calls including stopping calls. A pen substitute can check the trajectory, but cannot confirm how a local GUI looks. The historical circular self-similarity image is not this program’s output.

Permutations by insertion

Instead of choosing a first element, permute the first n−1 elements and insert the last element at every possible position. Each insertion keeps the existing elements.

def permutations_by_insertion(items: list[int]) -> list[list[int]]:
    if len(items) == 0:
        return [[]]
    smaller = permutations_by_insertion(items[:-1])
    last = items[-1]
    result: list[list[int]] = []
    for p in smaller:
        for position in range(len(p) + 1):
            result.append(p[:position] + [last] + p[position:])
    return result

print(permutations_by_insertion([]))
print(permutations_by_insertion([1, 2, 3]))
print(len(permutations_by_insertion([1, 1, 2])))

Its enumeration order differs from the main example. Repeated input values are still treated as separate positions and can produce repeated results.

Lexicographic permutations

Lexicographic order compares sequences at their first differing position. It does not require the values inside each permutation to increase. With distinct ascending input, choosing candidates from smallest to largest and completing one branch before starting the next enumerates full permutations lexicographically.

def lexicographic_extensions(prefix: list[int],
                             remaining: list[int]) -> list[list[int]]:
    if len(remaining) == 0:
        return [prefix.copy()]
    result: list[list[int]] = []
    for i in range(len(remaining)):
        rest = remaining[:i] + remaining[i + 1:]
        result.extend(lexicographic_extensions(
            prefix + [remaining[i]], rest))
    return result

def lexicographic_permutations(items: list[int]) -> list[list[int]]:
    return lexicographic_extensions([], items)

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

This code does not sort or deduplicate its input. Distinct ascending values are a precondition for the stated ordering. The older heading “Increasing permutations” referred to lexicographic full permutations, not strictly increasing combinations.

Partial permutations and combinations

Choose k elements from n distinct elements. A k-permutation counts order; a combination does not. Thus (1, 2) and (2, 1) are different permutations but the same combination. These standard-library calls show the difference for 0 ≤ k ≤ n.

from itertools import permutations, combinations

items = [1, 2, 3]
k = 2
ordered = list(permutations(items, k))
unordered = list(combinations(items, k))
print(ordered)
print(unordered)
print(len(ordered), len(unordered))
print(list(permutations(items, 0)))
print(list(combinations(items, 0)))

The counts are six and three. At k = 0, both have one empty tuple. A recursive partial permutation can choose any unused element next. A combination search instead advances through candidate indices in a fixed order, so different orders of the same selection are not counted again.

Displaying nested results with pprint

The standard-library pprint formats nested data for display. It preserves the order of this example’s lists, does not deduplicate entries, and does not mutate the input. Dictionaries are different: by default, their keys are sorted for display, so the displayed order can differ from the dictionary’s iteration order.

from itertools import permutations
from pprint import pprint

results = [list(p) for p in permutations([1, 2, 3])]
pprint(results, width=20)
print(len(results))

Queens by full column enumeration

Every permutation of 0..n−1 places one queen in each row and each column. Only diagonal checks remain. This is the alternative used in the older material.

from itertools import permutations

def diagonals_clear(queens: tuple) -> bool:
    for row in range(len(queens)):
        for earlier in range(row):
            if abs(row - earlier) == abs(queens[row] - queens[earlier]):
                return False
    return True

n = 8
candidates = 0
solutions = 0
for queens in permutations(range(n)):
    candidates += 1
    if diagonals_clear(queens):
        solutions += 1
print(candidates, solutions)

It examines 40320 = 8! complete column permutations and finds 92 solutions. Backtracking in the main section rejects conflicts in partial solutions, before generating every complete candidate. Equal solution counts do not mean equal computational effort.

Fibonacci with an array

Both iterative Fibonacci examples take a nonnegative integer index n. Handle zero before constructing a list for F(0)..F(n). Assigning values[1] unconditionally would index past the end for n = 0.

def fib_array(n: int) -> int:
    if n == 0:
        return 0
    values = [0] * (n + 1)
    values[1] = 1
    for i in range(2, n + 1):
        values[i] = values[i - 1] + values[i - 2]
    return values[n]

print([fib_array(n) for n in range(10)])

Each term is computed once, but the list stores every earlier term. Those terms are growing integers, so the element count is not the whole storage cost in bytes.

Fibonacci with two variables

Before update i, a = F(i) and b = F(i+1). After it, a = F(i+1) and b = F(i+2). Python evaluates both right-hand values before rebinding the names.

def fib_pair(n: int) -> int:
    a = 0
    b = 1
    for _ in range(n):
        a, b = b, a + b
    return a

print([fib_pair(n) for n in range(10)])
print(fib_pair(25))

Only two adjacent values are retained, rather than an array of all terms. The integer objects themselves still grow with n. The older two-variable version had correct initial values; the zero-input bug belonged to its array version.

State updates in a while loop

Euclid’s algorithm can update one parameter pair directly. After each loop iteration, (a, b) is the pair a recursive call would receive. Both expressions on the right use the old values.

def gcd_loop(a: int, b: int) -> int:
    while b != 0:
        a, b = b, a % b
    return a

print(gcd_loop(48, 18))
print(gcd_loop(0, 5))

No unfinished outer arithmetic needs to be retained here. Other recursive tasks may need a record of operations to perform after their smaller tasks finish; this simple conversion does not generalize to every recursive program.

Subproblems for coin combinations

The lab’s coin task assumes a nonnegative amount and distinct positive integer denominations. Order is not counted. A zero denomination would fail to reduce the amount when used; duplicate denominations can double-count choices.

Split on the current denomination: use it once and keep it available, or stop using it and continue with the remaining denominations. Amount zero has one empty combination. A positive amount with no denominations has none. If a recursive step permits a negative amount, that branch contributes zero.

A decreasing measure is “remaining amount plus the number of remaining denominations”: using a positive coin lowers the first part, while dropping a denomination lowers the second. Implement the combination of the two counts independently in the lab, taking care not to count different coin orders as new solutions.

Adjacent-peg Hanoi: the decomposition

The solo assignment permits only A ↔ B ↔ C. A direct move between A and C is forbidden. The ordinary Hanoi program’s largest-disk endpoint move therefore cannot be reused unchanged.

An endpoint-to-endpoint transfer decomposes into three transfers of n−1 disks between endpoints, interleaved with the largest disk’s adjacent moves A → B and B → C. Before either largest-disk move, the smaller stack must be positioned so that it does not obstruct that move.

For minimum endpoint-transfer counts, this gives T(0) = 0, T(n) = 3T(n−1) + 2, and T(n) = 3ⁿ−1. For n = 0..5, the values are 0, 2, 8, 26, 80, 242. This is a decomposition and count relationship, not a complete instruction generator. The argument order, sequence construction, legality checks, and minimum-count justification remain assignment work.