코딩테스트를 처음 준비할 때, 알고리즘 중 재귀함수가 너무 무서웠다 ㅠㅠ
재귀함수, 뭔가 이름도 무서운데... 계속 자기 자신을 호출한다고...?? 😱

이름부터 공포 그 자체였지만, 피할 수 없는 친구였기에
'파이썬 알고리즘 인터뷰' 책을 통해 끙끙대며 이해했던 기억이 있다.

이해할땐 정말 힘들었는데...
신기하게도 이해하고 나니 재귀함수로 푸는 문제는 다른 방식 (while 등등) 으로 푸는 방법이 떠오르질 않는다.

아무튼, 최근 프로그래머스에서 문제를 풀고 있는데, 하노이의 탑이라는 문제가 있었다!
처음엔 재귀 문제인 줄 모르고, 이 방법 저 방법 생각했는데..
아니 이문제를 어떻게 풀어...? 하는 도중
너무 앞이 막막한 나머지 풀이를 봤는데, 재귀함수로 완전 깔끔하게 풀리는 것을 보고 잠시 멍했었다.

피보나치 수열 같은 문제는 처음 딱 보자마자 재귀라는 느낌이 확 드는데, 하노이의 탑은 전혀 그런 느낌이 들지 않았다 ㅠㅠ

해설을 보고도 한동안 이해가 되지 않았는데, 여러 해설 동영상을 유튜브에서 보고 이제는 조금 이해가 된다!

내 기준 가장 이해가 잘 되었던 해설 강의

알고리즘 이해

간단하게 정리해보면 이렇다.
(그림은 n = 2 일 때)

1. n-1개의 원판을 경유지로 옮긴다.

2. 가장 큰 원판을 목적지로 옮긴다.

3. 1번에서 경유지로 옮겨놓은 n-1개의 원판들을 목적지로 옮긴다.

Python 코드

# a : 시작
# b : 경유
# c : 도착
def solution(n):
    
    def hanoi(n, a, b, c):
        
        # 원반이 1개일 경우 목적지로 이동
        if n == 1:
            answer.append([a, c])
            return
        
        # n-1개의 원반을 경유지로 이동
        hanoi(n - 1, a, c, b)
        
        # 가장 큰 원반을 목적지로 이동
        answer.append([a, c])
        
        # n-1개의 원반을 경유지에서 목적지로 이동
        hanoi(n - 1, b, a, c)
        
    answer = []
    hanoi(n, 1, 2, 3)
    
    return answer

이 문제가 코딩테스트에 출제될 것 같진 않지만,
재귀 문제가 출제될 가능성은 있기 때문에
하노이의 탑을 통해 재귀 함수와 좀 더 친숙해 지는 것이 좋을 것 같다 🤓