재귀 호출 뒤의 계산을 호출 앞으로 옮겨 리스트 처리를 반복으로 만들 수 있습니다. 꼬리 호출을 구별하고 어떤 식이 꼬리 위치를 유지하는지 살펴봅니다.
각 예제의 코드 전체를 플레이그라운드에서 실행하세요. 이름 있는 let이 처음이라면 재귀 가이드부터 읽으세요.
리스트의 합을 구하는 두 방법
다음 프로시저는 재귀 호출이 반환한 뒤 첫 항목을 더합니다.
(define (sum-list xs)
(if (null? xs)
0
(+ (car xs) (sum-list (cdr xs)))))
(sum-list (list 1 2 3))결과
6(1 2 3)을 받은 호출은 (2 3)의 합을 기다렸다가 1을 더합니다. 다음 호출은 (3)의 합을 기다렸다가 2를 더합니다. 리스트가 길수록 나중에 할 덧셈이 쌓입니다.
덧셈을 인자 안으로 옮기면 다음 호출 전에 계산할 수 있습니다.
(define (sum-list xs)
(let loop ((rest xs) (sum 0))
(if (null? rest)
sum
(loop (cdr rest) (+ sum (car rest))))))
(sum-list (list 1 2 3))결과
6sum은 지금까지의 합을 담는 매개변수인 누산기입니다. 각 호출은 다음 합을 계산한 뒤 loop를 호출합니다. 그 결과를 그대로 반환합니다.
호출 결과를 그대로 현재 프로시저의 결과로 반환하는 자리를 꼬리 위치라고 합니다. 리스펙스는 현재 프로시저가 반환한 뒤 이어서 할 일인 연속을 재사용합니다. 꼬리 호출마다 결과를 기다리는 호출을 더 쌓지 않습니다. 이 동작을 올바른 꼬리 호출이라고 합니다.
1만 번 반복하기
(let loop ((n 10000) (acc 0))
(if (= n 0)
acc
(loop (- n 1) (+ acc 1))))결과
10000각 호출은 n을 줄이고 acc를 늘립니다. 다음 호출이 선택된 if 분기의 마지막 동작입니다. 1만 번을 반복해도 결과를 기다리는 호출의 깊이는 일정합니다.
프로시저가 서로를 호출하는 상호 재귀에도 같은 규칙이 적용됩니다.
(letrec ((even-count? (lambda (n)
(if (= n 0) #t (odd-count? (- n 1)))))
(odd-count? (lambda (n)
(if (= n 0) #f (even-count? (- n 1))))))
(even-count? 10000))결과
#t두 프로시저는 서로의 결과를 그대로 반환합니다. 번갈아 호출해도 꼬리 호출을 유지합니다.
꼬리 위치 짚기
프로시저 본문의 마지막 식부터 살펴보세요. 어떤 형식이 꼬리 위치에 있다면 아래 부분도 꼬리 위치를 유지합니다.
| 형식 | 꼬리 위치 |
|---|---|
let, let*, letrec, begin | 본문의 마지막 식 |
if | 결과를 반환하는 두 분기 |
cond, case | 선택된 절의 마지막 식 |
and, or | 마지막 피연산자 |
when, unless | 실행하는 본문의 마지막 식 |
do | 다음 반복 호출과 마지막 결과 식 |
(apply proc args) | proc 호출 |
(call-with-values producer consumer) | consumer 호출 |
조건을 검사하는 식과 호출 인자는 결과를 사용하기 전에 평가합니다. 이 자리들은 꼬리 위치가 아닙니다.
| 프로시저의 꼬리 위치에 놓인 식 | loop 호출은 꼬리 호출인가요? |
|---|---|
(if done? answer (loop next)) | 예. 호출 결과를 그대로 반환합니다. |
(begin (display x) (loop next)) | 예. 마지막 식입니다. |
(+ x (loop next)) | 아니요. 그 결과로 덧셈을 해야 합니다. |
(map loop items) | 아니요. map이 각 loop 호출의 결과를 모읍니다. |
(apply loop args) | 예. apply가 꼬리 위치를 유지합니다. |
call-with-values에서는 producer를 실행한 뒤 consumer를 실행합니다. 꼬리 위치를 이어받는 호출은 consumer입니다.
자원 한도 살펴보기
꼬리 호출은 결과를 기다리는 호출의 깊이를 일정하게 유지합니다. 프로그램은 여전히 반복마다 계산하며 데이터를 만들 수도 있습니다.
실행 한도를 묶은 자원 프로파일은 계속 적용됩니다. 꼬리 위치가 아닌 재귀 호출은 깊이 한도에 도달할 수 있습니다. 꼬리 재귀 반복도 실행 작업량 같은 다른 한도에 도달할 수 있습니다.
같은 실행 조건에서는 자원 한도에 따른 결과가 같습니다. 자원 오류 기록에는 실행기 식별자와 프로파일 값과 도달한 한도가 들어 있습니다. 자세한 내용은 결정성과 자원을 보세요.