[TIL, 일일 회고] 2025.02.05 - 하노이 탑 알고리즘, 왜 재귀여야 할까❓

개요

하노이 탑 알고리즘은 다음과 같은 규칙을 가집니다.

• 한 번에 하나의 원반만 이동 가능
• 큰 원반이 작은 원반 위에 올 수 없음

이러한 규칙을 보면 맨 위의 원반부터 이동하므로 선입선출 구조인 큐나 배열의 사용을 고려할 수 있습니다. 하지만 하노이 탑은 대표적인 재귀 문제로 알려져 있습니다.

 

본 글에서는 하노이 탑 알고리즘에서 재귀 호출이 더 적합한 이유에 대해서 정리하고자 합니다.

 

왜 하노이 탑 문제에서 재귀를 사용해야할까❓ 

하노이 탑 문제 간단 소개

• 하노이 탑은 세 개의 기둥과 크기가 다른 원판들로 구성된 퍼즐입니다.
• 모든 원판을 처음 기둥에서 마지막 기둥으로 옮기되, 큰 원판 위에 작은 원판만이 올 수 있습니다.
• 이러한 분할 정복(Divide and Conquer) 방식은 재귀 호출과 자연스럽게 어울립니다.

---

1. 문제의 자기 유사성

 

• 하노이 탑은 "더 작은 하노이 탑 문제"로 나눌 수 있습니다.
• n개의 원판을 이동하는 문제는 "(n-1)개의 원판을 이동하는 문제"로 분해할 수 있습니다.

2. 상태 관리의 단순화

 

 

• 큐나 배열을 사용하면 각 기둥의 상태를 직접 관리해야 합니다.
• 반면 재귀를 사용하면 "어떤 원판을 어디로 옮길지"에만 집중할 수 있습니다.
• 재귀 호출의 콜 스택이 자연스럽게 원판의 순서를 보장합니다.

3. 직관적인 문제 해결 방식

 

 

• 큰 문제를 동일한 형태의 작은 문제로 나누어 해결하는 방식이 직관적입니다.
• 원판 3개를 옮기는 과정을 생각해보면:
  • 위의 2개 원판을 보조 기둥으로 이동
  • 가장 큰 원판을 목적지로 이동
  • 2개 원판을 다시 목적지로 이동

4. 코드의 간결성

 

 

• 반복문으로 구현할 경우 여러 조건문과 상태 체크가 필요합니다.
• 재귀를 사용하면 문제의 본질적인 로직만 남겨 코드가 간결해집니다.
• 코드의 가독성과 유지보수성이 향상됩니다.

5. 스택을 활용한 비재귀적 접근 가능성

• 하노이 탑 문제는 본질적으로 재귀적이지만, 명시적으로 스택(Stack) 자료구조를 활용하면 반복문으로도 구현할 수 있습니다.
• 그러나 이 방법은 재귀 호출이 내부적으로 활용하는 콜 스택(Call Stack)을 직접 관리해야 하므로 코드가 복잡해질 수 있습니다.