Рекурсия без роста продолжения

Проверьте запуском

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.
В тестах ограничивайте вход и отличайте глубину continuation от стоимости выполнения.

Добавьте 5 во входной список. Каков результат и остаётся ли рекурсивный вызов хвостовым?

Ответ

Результат — 15. Меняются только входные данные; loop по-прежнему является последним действием выбранной ветви.

Хвостовая безопасность не завершает бесконечный цикл и не отменяет бюджеты ресурсов.

Для преобразования нехвостовой функции откройте главу о хвостовых вызовах, а для выбора fold — справочник процедур высшего порядка.