재귀 호출
(recursive call)
: 함수 내부에서 자기 자신(함수)를 또 호출하는 행위
: early return (멈춤코드) 없으면 무한 반복함
아래 그림 같은 경우는 반환값에 스스로를 불러오고 있다. 반복문과 차이가 뭔지 궁금하다.
1914번: 하노이 탑
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로
www.acmicpc.net
하노이 탑 문제를 풀다가 규칙을 찾았다.
a(N) : N번째 원판이 옮겨지는 수는
N-1개의 원판을 옮긴 다음 (= a(N-1)번)
맨 아래 제일 큰 원판을 비어 있는 장대에 옮긴 뒤 (= 1번)
2번째 줄에 옮겨놓은 N-1개의 원판을 3번 장대로 옮기는 수 (= a(N-1)번)
의 합과 같다.
즉,
a(N) = 2 * a(N-1) + 1
def Hanoi(N):
if N == 1:
return 1
return 2 * Hanoi(N-1) + 1