Advanced · Recursion · 160 of 264
Towers of Hanoi
Move n disks from peg A to peg C using peg B, one disk at a time, never putting a bigger disk on a smaller one. Solve it with a recursive function.
Input: n (1 to 6). Output: every move, like Move disk 1 from A to C
Examples
Input
2
Output
Move disk 1 from A to B Move disk 2 from A to C Move disk 1 from B to C
Input
1
Output
Move disk 1 from A to C
Input
3
Output
Move disk 1 from A to C Move disk 2 from A to B Move disk 1 from C to B Move disk 3 from A to C Move disk 1 from B to A Move disk 2 from B to C Move disk 1 from A to C
One more test checks other inputs when you press Check.
Stuck? The idea behind recursion
A recursive function calls itself on a smaller version of the problem, until it reaches a case small enough to answer directly (the base case).
Trust the smaller call to be right, and only work out how to build this answer from it.
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(5))Watch for: Without a base case, or if the problem doesn't get smaller, it never stops: Python gives up with a RecursionError.