dydsj0920   2년 전

재귀 함수가 간단할때는 어떤 순서로 돌아가는지 알겠는데요(스택의 원리)

재귀 함수안에 자기 자신을 호출하는 함수가 이렇게 2개가 들어가버리니까 머리가 터질거 같네요..

디버그를 찍어봐도 어떤식으로 돌아가는지 이해가 잘 안가는데..ㅜ

제가 너무 꼼꼼하게 살펴보는건가요? 그냥 외워서 풀어야 하는걸까요?

재귀함수를 정확히 이해하기 위한 팁이 궁금합니다ㅜㅜ

djm03178   2년 전

먼저 solve 함수의 호출이 무엇을 의미하는지를 파악하는 게 중요합니다.

n: 움직여야 할 원판의 높이

x: 현재 자리

y: 옮겨가야 할 자리

그러면 우선 간단하게 main에서 solve(n, 1, 3);은 n개의 원판을 1번 자리에서 3번 자리로 옮긴다는 뜻을 알 수 있죠.


그 다음, 각 호출 내에서 무엇을 해야 하는지 살펴봅시다.

예를 들어, 처음에 원판 5개를 1에서 3으로 옮겨야 된다고 생각해보세요. 이를 크게 3개의 작업을 쪼개어 보면,

1. 맨 밑판을 제외한 4개를 2에 옮긴다.

2. 맨 밑판을 3에 옮긴다.

3. 2에 쌓인 4개를 3에 옮긴다.

이 3개의 과정이 바로 solve, printf, solve의 의미입니다.

 6 - x - y는 가능한 모든 x와 y의 조합에 대해서 다음 호출 식을 구하는 공식인데요, x랑 y를 하나씩 넣어서 계산해보시면 잘 나오는 걸 볼 수 있습니다.


별로 설명한 게 없는 것 같은데, 다 설명됐습니다. 재귀의 마법입니다.

dydsj0920   2년 전

답변 감사합니다!

jh05013   2년 전

재귀함수를 이해할 때는 어떻게 돌아가는지 끝까지 살펴보는 게 아니라 그냥 한 번만 내려가는 것으로 충분한 것 같습니다.

윗분의 답변처럼 solve(n,x,y)가 "n개를 x에서 y로 옮긴다"임을 알고 있으면 solve(n-1,x,6-x-y)는 그냥 "n-1개를 x에서 6-x-y로 옮긴다"로 보기만 해도 전체 과정을 알 수 있습니다.

dydsj0920   2년 전

그렇군요 답변 감사합니다!

댓글을 작성하려면 로그인해야 합니다.