재귀 정복하기 (하노이 탑)-JS

하노이 탑은 유명한 재귀 문제 중 하나이다. 재귀에 대한 이해를 하기 위해서 하노이 탑을 푸는 아주 간략하게 설명하고자 한다(보다 자세한 설명은 이미 너무 많이 있음)

 

      function hanoi(n, start, des) {
        if (n === 1) console.log(`${start} to ${des}`);
        else {
          // 먼저 이동을 해야 한다.
          hanoi(n - 1, start, 6 - (start + des));
          //마지막 기둥을 옮겨야지
          console.log(`${start} to ${des}`);
          hanoi(n - 1, 6 - (start + des), des);
        }
      }

 

문제의 난이도와 관계없이 코드는 매우 간단하다....재귀의 가장 큰 아픔? 허무한 점인 것 같다...(재귀 너무 어려워....)

하노이 탑을 풀어봤으면 알 수 있듯이 결국은 f(n-1)을 중간 지점으로 이동시킨 후 가장 큰 disk?판?을 종착지로 이동 후 마지막으로 f(n-1)을 종착지로 이동하면 되는 원리이다. 원리는 간단하지만, 이 글의 작성 목적은 재귀의 접근법을 기록하기 위해서다. 일단 여러 자료를 참고한 결과 

 

• f(1)과 같이 문제의 가장 간단한 케이스에 대해서 먼저 접근 (보통 이것이 base case임)
• f(n-1)도 동일한 결과를 보여줄 것이란 믿음
• 위의 믿음을 기반으로 f(n)도 의도한 결과를 낼 것이라고 생각하는 것이다. 

재귀를 풀다보면 가장 중요한 것은 반복되는 패턴을 빠르게 찾고 해당 패턴을 이용해 더 큰 케이스에 대해서 동일하게 적용할 수 있도록 코드를 작성하는 것이다(사실 이게 너무 어렵다....그리고 패턴을 찾더라도 이것을 코드로 변환하는 것도 너무 어렵다)

 

위의 코드를 실행하면 아래와 같은 결과를 도출할 수 있다. 

재귀는 벡트레킹, DFS, DP 등 여러 알고리즘에서도 활용되는 중요한 기법으로 알고리즘을 정복하려면 필수적으로 정복해야 하지만, 너무 어렵다. 추후에 번뜩이는 팁 같은 걸 추가로 학습한다면 본 글에 기록하려 한다.....