다른 재귀문제를 몇몇 개 풀어봤지만 하노이탑은 그냥 형태를 기억해서 푸네요..

안녕하세요 HLM NT님.

하노이 타워를 공부하다가 너무 어렵게 느껴지셨나보군요... 😥

사실 HLM NT님이 질문하신 것 처럼 재귀로 문제를 해결할 때 영상에서 설명한 것 처럼 모든 함수를 호출해보며 콜스택을 따라가보는 경우는 거의 없을겁니다. 다만 어떤 원리로 동작하는지 알아보기 위해서 전부 따라가본 것이죠~

재귀적인 사고가 쉽지 않아서 답답하셨을 거라고 생각합니다.

재귀 문제를 해결하기 위한 접근 방식을 설명해보려고 하는데 도움이 되셨으면 좋겠습니다. 😊

재귀의 강력함은 '하위 문제가 해결됐다고 가정하고' 현재 문제를 풀 수 있다는 것입니다. 그리고 이렇게 해결했다면 문제가 복잡해져도 해결되죠.

따라서 하노이 타워도 하위 문제(n-1개의 원반을 목적지가 아닌 다른 기둥으로 옮기기)가 해결됐다고 가정하고 현재 문제에만 집중한 것입니다.

하노이 타워에서 재귀적인 사고는 HLM NT님께서 암기하신 3단계입니다.

만약 가장 큰 원반을 목표 기둥에 옮기는 하나의 문제만 생각한다면 n-1의 원반을 옮기는 문제는 이미 해결됐다고 가정합니다.

그러면 가장 큰 원반 하나를 옮기는 건 아주 쉽죠.

이렇게 현재 문제를 해결했다면 다음 하위 문제인 n-1 원반을 다시 목표 기둥으로 옮기는 걸 생각해야합니다.

재귀로 문제를 풀기 위해서는 하위 문제와 현재 문제를 잘 구분하는게 핵심이라고 볼 수 있습니다.

재귀적 사고는 사람 일반적인 사고방식과는 많이 다르므로 익숙해지려면 시간과 연습이 필요합니다.

지금 이해가 안가서 조금 답답하시더라도 여러번 접하다보면 실력이 느실거라고 생각합니다 ㅎㅎ

도움이 됐을까요? 😊