소스코드

import sys
input = sys.stdin.readline

N = int(input().strip())

def hanoi(n, start, end, middle):
	# 기저조건
	if n == 1:
		sys.stdout.write(f"{start} {end}")
		return

	hanoi(n-1, start, middle, end)
	sys.stdout.write(f"{start} {end}")
	hanoi(n-1, middle, end, start)
	
sys.stdout.write(f"{2**N - 1}\\n")
hanoi(N,1,3,2)

풀이

hanoi(3, 1, 3, 2)
├── hanoi(2, 1, 2, 3)
│   ├── hanoi(1, 1, 3, 2)
│   │   └── print: 1 → 3  ← 출력①
│   └── print: 1 → 2      ← 출력②
│   └── hanoi(1, 3, 2, 1)
│       └── print: 3 → 2  ← 출력③
├── print: 1 → 3          ← 출력④
└── hanoi(2, 2, 3, 1)
    ├── hanoi(1, 2, 1, 3)
    │   └── print: 2 → 1  ← 출력⑤
    └── print: 2 → 3      ← 출력⑥
    └── hanoi(1, 1, 3, 2)
        └── print: 1 → 3  ← 출력⑦

하노이의 탑은 옮기는 원판의 개수가 줄어들어도 문제의 처리 순서와 로직은 동일하다.

1. 가장 큰 원판을 제외한 n-1개의 원판을 임시 장대로 옮긴다
2. 가장 큰 원판을 목적지 장대로 옮긴다
3. 가장 큰 원판을 제외한 n-1개의 원판을 목적지 장대로 옮긴다

n이 더 작은 경우나 더 큰 경우를 생각해보면 좀 더 와닿을 것이다.

hanoi(2, 1, 3, 2)
├── hanoi(1, 1, 2, 3)
│   └── print: 1 → 2   ← 출력①
├── print: 1 → 3       ← 출력②
└── hanoi(1, 2, 3, 1)
    └── print: 2 → 3   ← 출력③

n이 2개인 경우도 동일한 패턴을 보이는 것을 잘 보면 찾을 수 있다.

1. 가장 큰 원판을 제외한 1개의 원판을 임시 장대로 옮긴다
2. 가장 큰 원판을 목적지 장대로 옮긴다
3. 가장 큰 원판을 제외한 1개의 원판을 목적지 장대로 옮긴다

흐름은 알겠는데 이걸 재귀함수로 구현을 못 하겠어요

아마 많은 분들이 예시를 적어보며 대충 흐름은 감을 잡았을텐데요, 왜 재귀함수로 구현해야하는지, 인자 구성은 왜 저래야하는지 등에 대해 설명해보겠습니다.

왜 재귀함수여야 할까요?

재귀가 적절한 이유는 다음과 같습니다: