R6RS Scheme: 적절한 꼬리 재귀
R6RS Scheme: 적절한 꼬리 재귀
Scheme 구현이 가져야 하는 적절한 꼬리 재귀(proper tail recursion)의 성질을 설명해요.
출처: 문서
본문
Scheme 구현은 *적절한 꼬리 재귀(properly tail-recursive)*여야 해요. 이는 꼬리 호출(tail call)이 상수 공간에서 수행될 수 있어야 한다는 요구예요. 적절한 꼬리 재귀는 반복 계산이 어떻게 기술되든 상수 양의 제어 스택 공간으로 실행될 수 있게 해요.
구체적으로, 꼬리 위치(tail position)에서의 프로시저 호출은 그 결과가 외부 호출의 반환 값으로 곧바로 전달되는 호출이에요. 적절한 꼬리 재귀 구현에서는 이러한 꼬리 호출이 새 스택 프레임을 쌓지 않고 호출자와 같은 프레임에서 수행되므로, 깊은 재귀도 스택 고갈 없이 실행될 수 있어요. 이 성질은 Scheme에서 반복을 일반적인 프로시저 호출로 표현할 수 있게 하는 핵심이에요.