하노이의 탑: 큰 원판 하나를 옮기기 위한 재귀적 순서

가장 큰 원판을 옮기려면 그 위의 작은 원판을 먼저 비워야 합니다. 하노이는 작은 묶음을 치우기, 큰 원판 옮기기, 작은 묶음 덮기의 세 단계로 같은 문제를 반복합니다.

선수 지식: 재귀의 기저 조건과 호출·복귀, 배열에 결과를 모으는 방법

• 출발·도착·보조 기둥을 물리적 이름과 분리해 읽습니다.
• 재귀 호출 두 개 사이의 실제 이동을 추적합니다.
• 최소 이동 수와 결과 저장 비용을 구분합니다.

두 원판을 A에서 C로 옮기는 세 단계

원판은 한 번에 하나만 옮기며, 큰 원판을 작은 원판 위에 놓을 수 없습니다. A에 작은 원판 1과 큰 원판 2가 쌓여 있고 둘을 C로 옮기려 한다고 해 보겠습니다. 2를 바로 C로 옮기려면 위에 있는 1이 방해하므로, 먼저 1을 보조 기둥 B로 옮깁니다. 그다음 2를 A에서 C로 옮기고, 마지막으로 1을 B에서 C로 옮깁니다.

원판이 세 개여도 가운데 단계의 모양은 같습니다. 가장 큰 3을 A에서 C로 옮기기 전에 위의 두 개를 B로 치우고, 3을 옮긴 뒤 B의 두 개를 C로 옮깁니다. 두 개를 옮기는 일을 앞에서 구한 작은 문제에 맡기면 됩니다. 원판 하나를 직접 옮기는 동작과 원판 묶음을 옮기는 요청을 구분하는 것이 중요합니다.

함수의 from, to, spare는 각각 현재 문제의 출발·도착·보조 역할입니다. 기둥 이름 A, B, C는 고정되어도 역할은 호출마다 바뀝니다. 첫 작은 묶음을 A에서 B로 치울 때는 B가 도착이고 C가 보조입니다. 따라서 첫 호출의 인자 순서는 move(n - 1, from, spare, to)가 됩니다.

재귀 호출 사이에 큰 원판 이동을 둡니다

첫 작은 문제의 호출이 완전히 끝나야 큰 원판을 옮길 수 있습니다. 아직 작은 원판이 A에 남아 있는데 가운데 이동을 먼저 기록하면 실제 규칙을 어기게 됩니다. 반대로 큰 원판을 옮긴 뒤에는 작은 묶음의 출발이 B, 도착이 C, 보조가 A로 바뀌므로 두 번째 작은 문제의 인자는 move(n - 1, spare, to, from)입니다.

예제는 이동할 때마다 콘솔에 바로 쓰는 대신 {disk, from, to} 형태로 결과 배열에 모읍니다. 배열의 순서가 곧 실행 순서입니다. 화면 출력 방식과 이동을 결정하는 로직을 분리해 두면, 나중에 기둥 상태를 표시하거나 각 이동이 적법한지 검사할 때 같은 결과를 사용할 수 있습니다.

2개의 작은 문제와 1개의 이동이 만드는 횟수

n개의 원판에서 가장 큰 원판을 목적지로 옮기려면 위의 n – 1개를 다른 기둥으로 치워야 합니다. 가장 큰 원판이 목적지에 놓인 뒤에도 그 위에 n – 1개를 다시 쌓아야 합니다. 이 두 작업 사이에 큰 원판 이동이 한 번 필요하므로 T(n) = 2T(n - 1) + 1, T(0) = 0입니다.

이 관계를 펴면 원판 수가 1, 2, 3일 때 이동 수는 1, 3, 7이 되고 일반적으로 2ⁿ - 1입니다. 세 기둥에서 작은 원판을 큰 원판 위에만 놓는 규칙 아래, 이보다 적은 이동으로 필수인 두 작은 작업을 생략할 수 없습니다. 재귀 구성은 이 횟수를 실제로 달성하므로 최소 이동 순서를 만듭니다.

원판 하나를 더 넣을 때 결과가 거의 두 배로 늘어납니다. 따라서 문제 크기가 조금만 커져도 모든 이동을 출력하는 작업 자체가 커집니다. 메모이제이션으로 호출 계산을 아낀다고 해도 실제 이동 목록 2ⁿ – 1개를 전부 만드는 데 필요한 시간은 없앨 수 없습니다. 반환할 결과의 크기도 알고리즘 비용의 일부입니다.

원판 0개와 학습용 입력 범위를 먼저 처리합니다

원판 0개는 이미 옮길 것이 없으므로 빈 배열을 반환합니다. 재귀 함수는 n이 0이면 이동을 기록하지 않고 바로 끝납니다. 음수나 소수를 허용하면 n – 1을 반복해도 이 조건을 만나지 못할 수 있어, 호출 전 0~16의 정수인지 검사합니다. 16은 학습용 결과 크기를 제한하기 위한 상한이며 세 기둥의 이름도 서로 다른 비어 있지 않은 문자열이어야 합니다.

시간은 결과 이동 수에 비례한 O(2ⁿ)입니다. 동시에 쌓이는 호출은 한 경로의 깊이인 O(n)이지만, 이 구현은 모든 이동을 배열로 보관하므로 결과를 포함한 추가 공간은 O(2ⁿ)입니다. 결과를 보관하지 않고 하나씩 소비한다면 호출 스택 O(n)만 남습니다. 이 두 공간 기준을 섞으면 목록을 만드는 코드의 메모리를 과소평가하게 됩니다.

전체 코드와 직접 실행

개념을 읽었다면 아래 예제를 직접 실행하며 상태 변화를 확인할 수 있습니다.

function hanoi(count, from = 'A', to = 'C', spare = 'B') {
  if (!Number.isInteger(count) || count < 0 || count > 16) {
    throw new RangeError('원판 수는 0부터 16까지의 정수여야 합니다.');
  }
  const names = [from, to, spare];
  if (names.some(name => typeof name !== 'string' || name.length === 0) || new Set(names).size !== 3) {
    throw new TypeError('서로 다른 세 기둥 이름이 필요합니다.');
  }
  const moves = [];
  function move(n, start, destination, auxiliary) {
    if (n === 0) return;
    move(n - 1, start, auxiliary, destination);
    moves.push({ disk: n, from: start, to: destination });
    move(n - 1, auxiliary, destination, start);
  }
  move(count, from, to, spare);
  return moves;
}

console.log(JSON.stringify(hanoi(2)));
console.log(hanoi(3).length);
console.log(JSON.stringify(hanoi(0)));

node javascript-hanoi-recursion.mjs

[{"disk":1,"from":"A","to":"B"},{"disk":2,"from":"A","to":"C"},{"disk":1,"from":"B","to":"C"}]
7
[]

비용과 적용 범위

시간: O(2ⁿ)

공간: O(2ⁿ), 결과 제외 호출 스택 O(n)

분석 조건: 원판 n은 0~16의 정수입니다. 세 기둥의 표준 하노이 규칙을 따르며 2ⁿ – 1개의 이동 객체를 배열에 보관합니다.

직접 확인해 보기

원판 3개를 A에서 C로 옮길 때, 원판 3을 옮기기 직전 작은 두 원판은 어디에 있나요? 전체 이동에서 원판 3은 몇 번째에 움직이나요?

함께 읽을 글

• 자료구조 스택 쉽게 이해하기: push pop으로 문제 풀이 감 잡기 — 작은 묶음의 작업을 끝낸 뒤 이전 호출로 복귀하는 순서를 이해합니다.
• 기초 구현 패턴: 조건·정수 계산·순회·상태 갱신 — 한 단계에서 유지되는 규칙과 입력 검사를 복습합니다.

참고 자료

• MDN JavaScript Guide: Functions — 자기 자신을 호출하는 함수와 재귀 호출의 중첩, 기저 조건을 참고했습니다. 호출·복귀 추적과 입력 계약은 별도로 구성했습니다.
• Princeton Introduction to Programming — Recursion — 하노이의 두 작은 문제와 가운데 원판 이동, 지수적으로 늘어나는 이동 수를 참고했습니다. 추적과 입력 계약은 별도로 구성했습니다.