재귀함수 -파이썬(하노이탑)

오늘은 알고리즘 공부를 하면서 재귀함수의 대표적인 문제인 하노이탑 문제를 정리를 해보았다

---

하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다.

게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다.

위키백과 참고

1. 한 번에 한개의 원판만 옮길 수 있다.
2. 큰 원판이 작은 원판 위에 있어서는 안 된다.

 

차례대로 설명해주겠다

먼저 3개의 기둥이 있고 첫번째 기둥을 시작으로두고 가운데에 있는 기둥을 보조, 끝에 있는 끝이라고 둡니다

 

첫번째 기둥에 원판이 1개가 있을때는

시작 기둥에서 끝에있는 기둥으로 옮기면 됩니다

이것을 파이썬 소스로 풀이를 하면

 

과정을 출력을 하고 마지막에 return으로 함수를 종료를 해줍니다

 

원판의 개수가 2개 이상일때는 함수안에다가 똑같은 함수를 넣어줍니다

두번째 공식인 "큰 원판이 작은 원판 위에 있어서는 안 된다."라는 것 때문에 보조 기둥에다가 원판을 넘겨줍니다

그러고 나서 마지막에있는 가장 큰원판을 옮겨주는 과정을 출력을 해줍니다

그리고 다음에 보조기둥에 있던 원판들을 차례대로 끝 기둥에 옮겨주는 함수를 한번 더 써줍니다

전체 함수로 보면 함수에 안에다가 똑같은 함수를 쓰는 재귀함수의 형태로 나타납니다

처음에는 보조 기둥으로 옮겨준다고 생각을하고, 마지막에 보조 기둥에 있던 원판들을 끝 기둥에 옮겨준다고 생각하면 됩니다

N = 1일때

N=2일때

N = 3일때

N = 4일때

 

이렇게 과정의 갯수를 출력을 하면 1, 3, 7, 15...으로 늘어나고

공식으로 

2ⁿ-1

나옵니다

※참고> 유튜브