Рекурсия

Начнём с трёх слов, которые встречаются на этой странице повсюду.

Продолжение это работа, которая останется после того, как нынешнее вычисление закончится. В (+ 1 (f x)) в момент вызова f обещание прибавить 1 на обратном пути и есть продолжение. Пока обещания ждут, они занимают место.

Хвостовая позиция это место, где такого обещания не остаётся. Когда результат вызова прямо становится результатом объемлющего выражения, на обратном пути делать нечего, поэтому нынешнее продолжение передаётся дальше, а новое не накапливается. Поэтому рекурсивный вызов в хвостовой позиции не занимает лишнего места, сколько бы он ни крутился.

Именованный let это let, сразу после которого написано имя. Это имя и становится тем, что вы вызываете, чтобы пройти цикл ещё раз. Ниже такое имя это loop.

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

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

10

null? спрашивает, пуст ли список. Для пустого списка ответ истинный.

Тот же цикл можно записать через do. Для каждой переменной do принимает начальное значение и то, каким оно станет дальше, а затем условие остановки и значение, которое возвращается при остановке.

(do ((rest (list 1 2 3 4) (cdr rest))
     (sum 0 (+ sum (car rest))))
    ((null? rest) sum))

10

do сводится к тому же циклу, что и именованный let, поэтому берите ту запись, которая читается лучше. Уберите значение после условия остановки, и цикл ничего не вернёт.

Разберите приём

1. Найдите базовый случай. Когда xs пуст, готовый ответ уже хранится в sum.
2. Уменьшайте остаток работы. (cdr xs) убирает ровно один элемент, поэтому любой конечный правильный список достигает базы.
3. Переносите ответ вперёд. Новый аккумулятор вычисляется до loop, и рекурсивный вызов остаётся последним действием.

Как рассуждать

• Передавайте аккумуляторы параметрами вместо работы после возврата рекурсии.
• Хвостовая позиция сохраняется в последних путях if, begin, and/or, cond, case, do, call-with-values и apply.
• В тестах берите небольшой конечный вход и отличайте глубину продолжения от стоимости выполнения.

Проверьте себя

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

Частая ошибка

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

Куда дальше

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

Правильные хвостовые вызовы · Процедуры высшего порядка