A First Taste of Algorithms

Lab 3: The Visible Staircase

✦ ✦ ✦

Accompanies Chapter 3. The chapter legitimized a strange object — a procedure that calls itself — and read its cost off a tree. In this lab the strange object runs on a real machine, the hidden staircase of calls becomes visible on the screen, and the n log₂ n bill gets audited.

1. A first self-call

Before towers, the smallest possible recursion — a countdown:

def countdown(n):
    if n == 0:
        print("liftoff")
        return
    print(n)
    countdown(n - 1)

countdown(5)

Read it against the chapter’s two rescue conditions. The self-call goes strictly downward (n - 1). The descent has a floor (n == 0, where the procedure acts alone and returns). Both present: legitimate. Run it, then trace it in your head the slow way: countdown(5) prints 5 and asks countdown(4) to do the rest, which prints 4 and asks countdown(3)… Every call trusts the smaller call completely. That trust is the whole technique.

2. Hanoi in seven lines

The chapter’s three-line plan — clear, cross, restack — translated nearly word for word:

def hanoi(n, source, target, spare):
    if n == 1:
        print("disk 1:", source, "->", target)
        return
    hanoi(n - 1, source, spare, target)      # clear the way (note: spare is the goal)
    print("disk", n, ":", source, "->", target)   # the big crossing
    hanoi(n - 1, spare, target, source)      # restack on top

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

Run it and check the seven moves against the solution your hands found with coins. Then the only part of this program that ever confuses anyone: the peg arguments swap roles at each call. In the first self-call, the spare peg is the destination — clearing the way means parking the small tower out of the way. Trace hanoi(2, "A", "B", "C") (just that call) on paper and confirm the pegs land where the plan demands.

How big a tower dares the machine? First predict from the chapter’s table how many moves hanoi(20, ...) would print, then don’t print them — counting wants a different version:

def hanoi_moves(n):
    if n == 1:
        return 1
    return hanoi_moves(n - 1) + 1 + hanoi_moves(n - 1)

print(hanoi_moves(10))
print(hanoi_moves(20))
print(hanoi_moves(30))

Check all three against 2ⁿ − 1. Then read the function once more: it is the recurrence M(n) = 2M(n−1) + 1, alive. The chapter’s cost equation and this cost program are the same sentence in two grammars.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses