ハノイの塔
ハノイの塔（ハノイのとう、Tower of Hanoi）はパズルの一種。 バラモンの塔または ルーカスタワー(Lucas’ Tower)[1]とも呼ばれる。
ハノイの塔
出典: フリー百科事典『ウィキペディア（Wikipedia）』
再帰で良く出てくるアレです。
説明を読むと納得はできるのですが、いまだに直感的に良く理解することができません。
多分自分には才能がないのだと思います。
Pythonで実装してみました。
コード
# 入力
N = int(input())
# 三本の杭を作る
start = list(range(N, 0, -1))
tmp = []
end = []
def print_piles():
print('----')
print('s: ', start)
print('t: ', tmp)
print('e: ', end)
def hanoi(n, start, end, tmp):
if n <= 0:
return
# n-1 まで全てをstartからtmpに移動。
hanoi(n-1, start, tmp, end)
# n をstartからendに移動。
end.append(start.pop())
print_piles()
# n-1 をtmpからendに移動。
hanoi(n-1, tmp, end, start)
print_piles()
hanoi(N, start, end, tmp)
参考サイト
ただし、棒a、bを0、1とすれば棒の総和 – (棒a + 棒b)で棒cを求めることができるので、
引数にわざわざ作業用の棒を渡さずにすっきり書けます。