TAKEAWAY 7.13 함수의 선행 조건을 명확하게 표현한다.

그러고 나서 10줄에서 a가 0인지 확인한다. 만약 그렇다면 b를 리턴한다. 이는 재귀 알고리즘에서 굉장히 중요한 단계다.

TAKEAWAY 7.14 재귀 함수를 실행하면 가장 먼저 종료 상태 검사를 한다.

종료 상태 검사를 누락하면 무한 재귀호출(infinite recursion)에 빠질 수 있다. 그러면 자기 자신을 복제해서 호출하는 과정을 계속 반복하다가 시스템 리소스가 모두 소진되면 프로그램의 실행이 멈춘다. 최신 시스템은 메모리 용량이 커서 시스템이 멈출 때까지 상당한 시간이 걸릴 수 있다. 직접 확인해 보지는 않기 바란다.

종료 상태가 아니라면 b%a를 계산해서 rem에 대입한다(11줄). 그 후 rem과 a에 대해 gcd2를 재귀호출하고, 그 결과로 나온 값을 리턴한다.

그림 7-2는 gcd2(18, 30)을 호출한 후에 발생하는 재귀호출 과정을 표현한 것이다. 여기서는 네 단계까지만 표시했다. 각 단계마다 a, b, rem 변수는 별도의 복제본을 사용한다.

▲ 그림 7-2 gcd2(18, 30)의 재귀호출 과정