Вы можете превратить рекурсивную обработку списка в цикл, перенеся вычисления перед следующим вызовом. Здесь вы научитесь находить хвостовые вызовы и определять, какие выражения сохраняют хвостовую позицию.
Запустите каждый пример целиком на площадке. Если именованный 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))Результат
6Здесь sum — аккумулятор, параметр с текущей суммой. Каждый вызов вычисляет следующую сумму до вызова loop. Результат loop возвращается напрямую.
Вызов находится в хвостовой позиции, если его результат сразу становится результатом вызывающей процедуры. Лиспекс повторно использует текущее продолжение, то есть работу, оставшуюся после возврата из этой процедуры. Каждый хвостовой вызов обходится без добавления ещё одного ожидающего вызова. Это поведение называется правильными хвостовыми вызовами.
Повторите десять тысяч раз
(let loop ((n 10000) (acc 0))
(if (= n 0)
acc
(loop (- n 1) (+ acc 1))))Результат
10000Каждый вызов уменьшает n и увеличивает acc. Следующий вызов является последним действием выбранной ветви if. За десять тысяч итераций глубина ожидающих вызовов остаётся постоянной.
То же правило действует для взаимной рекурсии, когда процедуры вызывают друг друга.
(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.
Учитывайте лимиты ресурсов
Хвостовые вызовы сохраняют постоянную глубину ожидающих вызовов. Программа по-прежнему выполняет вычисления на каждой итерации и может выделять память для данных.
Выбранный профиль ресурсов, то есть набор лимитов выполнения, продолжает действовать. Нехвостовая рекурсия может достичь лимита глубины. Хвостовой цикл может достичь другого лимита, например бюджета работы вычисления.
При одинаковых заданных условиях выполнения лимиты ресурсов дают повторяемые результаты. Запись об ошибке ресурсов содержит идентификатор исполнителя, значения профиля и достигнутый порог. Подробнее — в разделе о детерминизме и ресурсах.