[코드잇] 알고리즘 - 재귀함수2

이진 탐색

이진 탐색 알고리즘을 이미 반복문으로는 구현해 보셨죠? 이번에는 재귀적으로 문제를 해결해 보세요.

반드시 재귀(recursion)의 개념을 사용하셔야 합니다. 코드 구현이 꽤 어려우니, 천천히 고민해 보시기 바랍니다. 다른 재귀 문제를 풀 때와 마찬가지로 base case와 recursive case를 생각해 내는 것이 핵심입니다!

---

하노이의 탑

하노이의 탑 게임 아시나요? 이 게임의 목표는 왼쪽 기둥에 있는 원판들을 모두 오른쪽 기둥으로 옮기는 것입니다. 지켜야할 규칙은 두가지입니다:

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

(출저: 위키피디아)

하노이의 탑 게임의 해답을 출력해주는 함수 hanoi를 쓰세요. hanoi는 파라미터로 원판 수 num_disks, 게임을 시작하는 기둥 번호 start_peg, 그리고 목표로 하는 기둥 번호 end_peg를 받고, 재귀적으로 문제를 풀어 원판을 옮기는 순서를 모두 출력합니다.