컴파일러
위의 함수의 마지막 재귀 호출에 꼬리 호출 최적화를 적용하면 어떤 효과가 있는가?
int fact(int n, int acc) {
if (n <= 1) return acc;
return fact(n - 1, acc * n);
}- A재귀 횟수가 절반이 되어 계산 결과도 2배 빠르게 구해진다
- B함수가 인라인 전개되어 재귀 자체가 상수로 치환된다
- C호출이 분기(점프)로 치환되어 재귀가 깊어도 스택이 늘어나지 않는다
정답과 해설 보기
정답: C. 호출이 분기(점프)로 치환되어 재귀가 깊어도 스택이 늘어나지 않는다
이 함수의 재귀 호출은 함수의 마지막 처리이며 그 결과를 그대로 반환하고 있습니다(꼬리 호출). 호출 뒤에 남는 처리가 없으므로 현재 함수의 스택 프레임을 재사용하고, 인수를 덮어쓴 뒤 함수의 처음으로 점프하는 형태로 변환할 수 있습니다. 이로써 루프와 같은 동작이 되어 재귀가 아무리 깊어도 스택이 늘어나지 않으며 넘칠 염려가 없어집니다. 재귀 횟수는 변하지 않고, n은 실행 시에 정해지므로 상수로 할 수 없습니다.
- A. 반복 횟수는 변하지 않습니다.
- B. n은 실행 시에 정해지므로 상수로 치환할 수 없습니다.
- C. 올바릅니다. 점프로 치환되어 스택이 늘어나지 않습니다.