하노이 탑은 프랑스의 수학자 에두아르 뤼카가 1883년 소개한 유명한 문제로, 아래 그림을 보시면 익숙할 것이라고 생각이 듭니다. 옮기는 과정에서 작은 원반 위에 큰 원반이 놓일 수 없으며, tower 1에 있던 모든 원반이 tower 3으로 이동을 시키는 문제입니다.

어떻게 정의해야할지 잘 떠오르지 않아서 실제로 원반을 하나씩 옮겨보았습니다.
문제를 작게 만드어 해결하고 이후에 확대하는 방법이 알고리즘 문제를 푸는데 도움이 될 수 있습니다.
일단 3개의 원반을 A에서 C로 이동을 한다고 가정합니다.

친절하게 설명이 되어있는 블로그를 참조했습니다.
세개을 원반을 이동할 때 얻을 수 있는 아이디어 세 가지가 있습니다.
원반이 한 개 일때는 그냥 목표지점으로 이동을 하고 끝난다.
가장 큰 마지막 원반이 목표 지점에 도달하게 되면 그 원반을 더 이상 이동을 하지 않는다.
시작과 목표 원반이 아닌 보조원반에 가장큰 원반을 제외하고 모든 원반이 이동이 되는 과정이 있다.
def hanoi(원반개수, 시작, 끝, 보조)
if 원반이 하나일 때:#시작에서 끝으로 한 번 이동시킨다.
print(시작, 끝)
return
else:
#원반개수-1만큼 보조 원기둥으로 이동시켜야한다
hanoi(원반개수-1, 시작, 보조, 목표)
#이동시킨다.
print(시작, 보조)
#보조 원기둥에 있는 원반을 목표 원기둥으로 이동시켜야 하기 때문에 보조기둥을 시작기둥으로 변경한다.
hanoi(원반개수-1, 보조, 목표, 시작)