재귀란 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻한다. 즉, 어떤 함수를 호출하면 그 안에 어떤 함수를 또 호출하여 반복한다는 뜻이다. 쉽게 이해하려면 엘리베이터 거울을 생각하면 좋을 것 같다! (내가 이걸로 이해했다.🥶)
처음에는 굉장히 생소한 이름이었지만 Node.js를 공부하며 콜백 지옥 이라는 내용을 접했는데, 여기서 콜백 이 재귀 함수의 개념을 포함하고 있다고 한다.(맞을거다..ㅎ)
사이버다임 면접을 준비하면서 재귀 함수에 대한 문제가 나온다는 이야기를 들었고, 이를 공부하기 위해서 하노이의 탑 문제를 풀어 봤는데 손으로 직접 그려 보기 전까지는 전혀 이해하지 못했다. 근데 한번 손으로 그려 보니까 완벽하지 않지만 대략적으로 재귀에 대한 틀이 잡힌 것 같다.
(정작 사이버다임 코딩테스트에서는 팩토리얼에 대한 문제가 출제됐다. 다음에 기회가 된다면 다뤄 봐야겠다.)(자세한 내용은 아래 블로그를 참고.)
반드시 알아야하는 알고리즘 top 8 - 1. 재귀 알고리즘
하노이의 탑은 아기들이 가지고 노는 장난감같이 생겼는데, 나는 어렸을 때 이런 장난감은 안 갖고 놀아서 그런지 굉장히 익숙하지 않았다.
그래서 손으로 직접 그려 보기도 하고, 책도 참고하고, 유튜브 영상도 시청했다. 가장 쉽게 설명한 영상은 얄팍한 코딩 사전님이 올려 주신 영상이다.
https://www.youtube.com/watch?v=aPYE0anPZqI
그래서, 나는 공부한 것을 바탕으로 이렇게 써가며 문제를 풀어 봤다.
처음에는 내가 나를 호출하고, 호출당한 내가 또 나를 호출하고, 호출당한 내가 호출한 내가 또 나를 호출하고... 이렇게 끝없이 반복되는 것이 너무 어려웠다. 여기서 함수를 호출하는 조건을 이해하고, 이 것을 위의 2 번째 그림으로 그려 보면 한층 더 이해하기 쉬워진다.
그래서 나는 이렇게 코드를 짰다. (사실 하노이의 탑 문제는 거의 모든 사람들의 풀이가 비슷하다.)
해당 코드에서 중요한 부분은 재귀적으로 반복하는 move() 함수도 있지만, 6 이라는 숫자는 왜 나왔는지를 파악하는 것이 중요하다.
위의 노트 내용을 참고하면, 결과적으로 3번 원반부터 1번 원반까지 3번 기둥으로 옮겨야 하는 것이 관건이다.
여기서 3번 원반을 3번 기둥으로 옮기기 위해서는 2번 원반을 먼저 다른 기둥으로 옮겨야 하고, 2번 기둥을 옮기기 위해서는 1번 원반을 먼저 다른 기둥으로 옮겨야 한다.
즉, 3번 원반을 3번 기둥을 옮기기 위해서 가장 기초가 되어야 하는 일이 1번 원반이 다른 기둥으로 이동해야 한다는 점이다.
(결과를 파악하고 결과를 도달하기 위해 시작점을 파악한다.)