[파이썬 프로그래밍] 25화 재귀함수(recursive function)
예전에 함수에 대해서 쭈~욱 진행하다가 반복문과 조건문에 대해서 진도가 나갔습니다.
이번에 다시 함수쪽에서 중요한 개념중 하나인 '재귀함수' 에 대해서 학습을 해보도록 하겠습니다.
재귀적 함수호출 의 예를 들떄는 '하노이의 탑' 을 빗대어서 설명을 드릴 수 있습니다.
하노이의 탑
예전에 kbs 스폰지 방송에서 '공부잘하는법' 편인가요? 거기서 하노이탑(Hanoi Tower)에 대해서
소개 된 적이 있습니다. 그떄 저도 구입했었는데 그것이 위의 그림과 같이 생긴 모습입니다.
하노이의 탑의 원리는, 하나의 축에 크기가 각기 다른 원반이 쌓여 있고, 제 3의 축을 이용하여
작은 원반 위에 큰 원반이 놓여지지 않도록 하면서 한번에 한장씩 움직여서 다른 축으로 원반을 이동시키는
퍼즐입니다.
자바나, C언어 학습시에도 '재귀적 프로그램'의 예로 많이 등장하죠.
이번에 파이썬 25화 재귀적 함수호출에 대해서 학습할때도 역시 이 예를 통해서
공부해 보도록 하겠습니다.
재귀함수 예제
def 로 함수를 만들겠다고 선언하고 factorial 이라는 이름의 함수명을 만듭니다. 인자로 a를 넣구요
factorial 의 이름은 '계승' 이라는 뜻입니다.
이 함수는 자기자신을 호출하는 재귀함수인데 -1씩 감소시키며 호출합니다.
if문으로 a == 1 이라는 조건을 만족하면 1이 반환됩니다.
1*2*3*4*5 처럼 진행됩니다. 그래서 5까지 계산하면 결과 값으로 '120'이 출력 되는 것이죠.
이번에는 아까 위에서 설명한 '하노이탑'을 이용한 예제를 해보겠습니다.
참고페이지: http://rosettacode.org/wiki/Towers_of_Hanoi#Python
원리:
1. 기둥 1에서 N - 1개의 원반을 기둥 3을 이용해 기둥 2로 옮김
2. 기둥1에서 1개의 원반을 기둥3으로 옮김
3. 기둥 2에서 N - 1개의 원반을 기둥 1을 이용해 기둥 3으로 옮김
