재귀 호출 없는 하노이타워

일반적으로 하노이 타워 코드는 재귀호출을 설명하기 위한 예시로 많이 사용된다.

 

하지만 재귀와 반복은 상호 대체 가능하므로, 하노이 타워를 재귀 호출 없이 반복문을 이용해 작성해보자.

비교를 위해 재귀 호출을 이용한 코드도 함께 작성했다.

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

struct CallStackElement
{
  int n;
  char from;
  char to;
  char aux;
  bool print;
};

void print_move(int n, char from, char to)
{
  cout << "Move disk " << n << " from " << from << " to " << to << endl;
}

void hanoi_loop(int n, char from, char to, char aux)
{
  stack<CallStackElement> callStack = {};
  callStack.push({n, from, to, aux, n == 1});

  while (!callStack.empty())
  {
    CallStackElement now = callStack.top();
    int n = now.n;
    char from = now.from;
    char to = now.to;
    char aux = now.aux;
    bool print = now.print;

    callStack.pop();

    if (print)
    {
      print_move(n, from, to);
      continue;
    }

    if (n > 1)
      callStack.push({n - 1, aux, to, from, false});
    callStack.push({n, from, to, aux, true});
    if (n > 1)
      callStack.push({n - 1, from, aux, to, false});
  }
}

void hanoi_recursive(int n, char from, char to, char aux)
{
  if (n == 1)
  {
    print_move(1, from, to);
    return;
  }
  hanoi_recursive(n - 1, from, aux, to);
  print_move(n, from, to);
  hanoi_recursive(n - 1, aux, to, from);
}

int main(void)
{
  hanoi_recursive(4, 'A', 'B', 'C');
  cout << "----------------------------------------" << endl;
  hanoi_loop(4, 'A', 'B', 'C');
  return 0;
}