함수 f(x, y)를 'y가 0이면 x를 반환하고, 그렇지 않으면 f(y, x mod y)를 반환한다'로 정의한다. f(84, 36)을 호출했을 때의 반환값과, f가 호출되는 횟수(첫 호출 포함)의 조합은?

정답: A. 반환값 12, 호출 횟수 3회

f(84, 36)은 84 mod 36 = 12이므로 f(36, 12)를 호출하고, 36 mod 12 = 0이므로 f(12, 0)을 호출하며, y가 0이므로 12를 반환합니다. 호출은 f(84, 36), f(36, 12), f(12, 0)의 3회이며, 이는 유클리드 호제법에 의한 최대공약수 계산입니다. 이 함수는 재귀 호출의 결과를 그대로 반환하는 꼬리 재귀이므로, 컴파일러가 꼬리 호출 최적화를 수행하면 루프로 변환할 수 있어, 호출이 깊어져도 스택을 계속 소비하지 않습니다.