Рекурсия

Запустите каждый пример целиком на площадке. Результат приведён под кодом.

Сложите четыре числа

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

10

Имя loop после let позволяет процедуре вызвать себя из собственного тела. Такая запись называется именованным let. Вызов процедурой самой себя называется рекурсией.

В xs хранятся элементы, которые ещё предстоит сложить. Параметр sum хранит текущую сумму. Параметр, который переносит промежуточный результат между вызовами, называется аккумулятором.

null? возвращает истину для пустого списка. Когда xs пуст, процедура возвращает sum без нового вызова. Этот случай остановки называется базовым случаем.

Каждый рекурсивный вызов получает (cdr xs), список без первого элемента. Поэтому любой конечный правильный список достигает базового случая. Для пустого входного списка результатом будет начальная сумма, 0.

Найдите хвостовой вызов

Аргументы (cdr xs) и (+ sum (car xs)) вычисляются до следующего вызова loop. Его результат сразу становится результатом текущего вызова. После возврата больше ничего складывать не нужно.

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

Каждый элемент всё равно требует вычислений. Время выполнения и память для данных зависят от программы и входа, а лимиты ресурсов продолжают действовать.

Запишите тот же цикл через do

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

10

Для каждой переменной указаны начальное и следующее значения. На каждом шаге do вычисляет оба следующих значения по текущим rest и sum. Когда rest пуст, цикл возвращает sum.

Лиспекс преобразует do в рекурсивный цикл с хвостовым вызовом. Если убрать выражение результата после условия остановки, do вернёт ноль значений. Полный синтаксис приведён в разделе об условиях и производных формах.

Измените вход

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

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

Готовые операции над списками собраны в справочнике процедур высшего порядка.