연속을 늘리지 않는 재귀

실행으로 확인하기

LISPEX

(let loop ((xs (list 1 2 3 4)) (sum 0)) (if (null? xs) sum (loop (cdr xs) (+ sum (car xs)))))

관측 결과

OUTPUT

기저 사례를 찾습니다. xs가 비면 답은 이미 sum에 있습니다.
남은 일을 줄입니다. (cdr xs)는 항목을 정확히 하나씩 덜어냅니다. 그래서 길이가 유한한 올바른 리스트는 반드시 기저 사례에 닿습니다.
답을 앞으로 넘깁니다. 다음 누산기를 loop을 부르기 전에 계산합니다. 그러면 재귀 호출 자체가 마지막 동작으로 남습니다.

재귀 호출이 값을 돌려준 뒤에 계산을 덧붙이지 마세요. 대신 누산기를 매개변수로 넘깁니다.
마지막 자리에 오는 if, begin, and·or, cond, case, do, call-with-values, apply 경로에서도 꼬리 위치는 그대로 유지됩니다.
테스트할 때는 입력 크기를 제한하세요. 연속 깊이와 실행 비용은 따로 구분해서 봅니다.

입력 리스트에 5를 하나 더 넣으면 결과는 무엇일까요? 재귀 호출은 여전히 꼬리 위치일까요?

답

결과는 15입니다. 바뀐 것은 입력 데이터뿐이므로 loop는 여전히 선택한 분기의 마지막 동작입니다.

꼬리 안전성은 무한 루프를 끝내 주거나 자원 예산을 없애 주지 않습니다.

꼬리가 아닌 함수를 바꿀 때는 꼬리 호출 매뉴얼을 보세요. 재귀 대신 fold를 고를 때는 고차 프로시저 레퍼런스를 보세요.