알아 보기

 

프로그램 5-2를 보면 단 세 줄밖에 되지 않는 gcd() 함수로 최대공약수를 구할 수 있는데 이것이 바로 재귀 호출의 매력입니다. 자기가 자기를 부르는 과정, 즉 꼬리에 꼬리를 무는 함수 호출은 처음에는 다소 혼란스럽지만, 한 번 익혀 두면 여러 가지 문제를 굉장히 단순하게 풀 수 있도록 하는 강력한 무기가 됩니다.

종이와 연필을 꺼내서 재귀 호출로 문제를 푸는 과정을 다음과 같이 직접 적어 보면 재귀 호출이 조금 더 익숙해질 것입니다.

 

gcd(60, 24)

→ gcd(24, 12)

    → gcd(12, 0)

        → 12 (b가 0이므로 종료 조건)

    → 12

→ 12 (최종 결과)

 

복잡한 재귀 호출을 알 것도 같고 모를 것도 같다고요? 컴퓨터 과학의 고전 문제라 불리는 ‘하노이의 탑’ 문제를 통해서 재귀 호출을 한 번 더 연습해 보겠습니다.