Free Recursion lessonsRecursion · Stage 2 · Divide and conquer · Step 3

Move the tower

Move a stack of discs from one peg to another by moving all but the biggest disc out of the way, then moving it, then moving the rest back on top. About 14 minutes.

Three pegs, one rule

A tower of discs, biggest at the bottom, sits on peg A. You must move all of it to peg C, one disc at a time, never placing a bigger disc on a smaller one. Peg B is a spare.

Think about the biggest disc. To move it from A to C, everything above it must be out of the way, parked on B. After moving the biggest disc, the tower on B has to go on top of it. Both of those jobs are the same puzzle with one fewer disc.

Move n − 1 discs: from A to the spare peg B.

Move the biggest disc: from A to C.

Move n − 1 discs: from B onto C.

In code

def countdown(n):
    if n == 0:
        return
    print(n)
    countdown(n - 1)
    print(n)      # after the call returns

Moves for 3 discs from A to C, in order.

A>C

A>B

C>B

A>C

B>A

B>C

A>C

leftright

Moving 3 discs A to C starts by moving the top 2 discs from A to B: A>C, A>B, C>B (the small disc steps aside, then the middle disc moves, then the small disc lands on it).

Move 1 of 4

Swap the roles of the pegs

In the first smaller move, the destination is the spare peg, and the old destination becomes the spare. In the second, the source is the spare peg. So the three pegs trade jobs from one call to the next. Keeping src, dst and via straight is the whole skill.

The base case is zero discs: nothing to move. You don't need to trace the many moves; trust each smaller call to move its smaller tower correctly.

Roles change: the spare and destination trade places.

Base case: zero discs means do nothing.

Quick check

How many moves does it take to move 4 discs?

Show the answer

15. Moving 3 discs takes 7, so 4 discs take 7 + 1 + 7 = 15.

Your problem

Move the tower

Three pegs are named "A", "B" and "C". A tower of n discs, biggest at the bottom, stands on peg A. Return the list of moves that transfers the whole tower to peg C, moving one disc at a time and never placing a bigger disc on a smaller one, using the fewest moves. Write each move as the peg it leaves, then a ">" sign, then the peg it goes to, such as "A>C". There is exactly one shortest list.

Example

n = 2 → ["A>B", "A>C", "B>C"]

0 ≤ n ≤ 8

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.