Recursion: Tower of Hanoi

Recursion: Tower of Hanoi

Three pegs A, B, C; peg A holds n disks stacked largest-at-bottom. Move them all from A to C: only one disk at a time, and a larger disk may never sit on a smaller one. Print every move, recursively.

The essence of recursion — split "move n" into two "move n−1" subproblems:

1. Move the top n-1 disks from from to via (using to as spare);
2. Move the largest disk from from directly to to (print this move);
3. Move those n-1 disks from via to to (using from as spare).

Base case: when n == 0 there is nothing to move (just return). Complete hanoi.

Pitfalls: (1) omitting the n == 0 base causes infinite recursion / stack overflow. (2) Pass the correct spare peg to each recursive call — first uses to as spare, third uses from; swapping them breaks the rule. (3) The printed move goes between the two recursive calls.

Input

• One line: integer n (0 ≤ n ≤ 12), the number of disks.

Output

• One move per line, formatted X -> Y (move from peg X to peg Y). n disks take exactly 2^n − 1 moves; n = 0 prints nothing.

Example: input 2 -> three lines A -> B / A -> C / B -> C.