Рекурсия и хвостовая рекурсия: TCO в Scheme и его отсутствие в CL

Рекурсия как естественный способ мышления в Lisp, хвостовая рекурсия, TCO в Scheme и его отсутствие в стандарте Common Lisp.

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

Зачем это: списки рекурсивны по своей природе

Lisp буквально назван в честь обработки списков (LISt Processing), а список — рекурсивная структура: это либо пустота nil, либо пара «голова + хвост-список». Поэтому самый естественный способ обойти список — рекурсия, повторяющая его форму: обработай голову, рекурсивно обработай хвост. Где императивный язык тянется за циклом и индексом, Lisp-программист пишет рекурсию, и она читается как определение: «сумма пустого списка — ноль; сумма непустого — голова плюс сумма хвоста». Рекурсия здесь не трюк, а основной строительный приём, и владеть ею нужно свободно.

(defun my-length (lst)
  (if (null lst)
      0                              ; база: пустой список
      (1+ (my-length (rest lst)))))  ; шаг: 1 + длина хвоста

(my-length '(a b c d))   ; => 4

Обратите внимание на анатомию: база (условие остановки) и шаг (сведение задачи к меньшей). Без базы рекурсия не завершится; без сведения к меньшему — тоже. Эти две части — обязательный каркас любой корректной рекурсии.

Есть проверенный способ думать рекурсивно, который помогает не запутаться. Не пытайтесь «прокрутить» рекурсию в голове на много уровней — это быстро перегружает память. Вместо этого доверьтесь индуктивному скачку веры: предположите, что рекурсивный вызов на меньшем входе уже работает правильно, и спросите себя только два вопроса. Первый: «верна ли база — то есть простейший случай, который я возвращаю напрямую?». Второй: «если рекурсия на хвосте уже дала верный ответ, правильно ли я достраиваю из него ответ для всего входа?». Если оба «да» — функция корректна по индукции, и не нужно представлять всю башню вызовов. Этот приём — главный навык рекурсивного мышления; он превращает «как это вообще работает» в две локальные, легко проверяемые проверки. Именно так математик доказывает по индукции, и рекурсия — буквально вычислительное воплощение индукции.

Древовидная рекурсия и накопители

Рекурсия бывает не только линейной. Когда функция вызывает себя дважды и более, получается древовидная рекурсия — ею естественно описываются деревья, переборы, числа Фибоначчи. Но древовидная наивная рекурсия легко становится экспоненциально медленной (как наивный Фибоначчи), поэтому важно понимать стоимость.

Полезно ещё различать прямую и взаимную рекурсию. Прямая — функция зовёт сама себя. Взаимная — две (или больше) функции зовут друг друга: классический пример — проверка чётности через пару even-p/odd-p, где «чётность n» определяется через «нечётность n−1», и наоборот. Взаимная рекурсия естественно описывает грамматики и разбор: «выражение состоит из термов, терм — из множителей, множитель — снова из выражения в скобках». В Common Lisp взаимно-рекурсивные локальные функции заводят через labels (он, в отличие от flet, позволяет функциям видеть друг друга). Понимание, что рекурсия бывает не только «сама в себя», расширяет арсенал: многие задачи естественнее раскладываются на несколько взаимодействующих функций.

;; взаимная рекурсия через labels (функции видят друг друга)
(defun parity (n)
  (labels ((my-even (k) (if (zerop k) t   (my-odd  (1- k))))
           (my-odd  (k) (if (zerop k) nil (my-even (1- k)))))
    (if (my-even n) 'even 'odd)))

(parity 10)   ; => EVEN
(parity 7)    ; => ODD

Отдельный важный приём — накопитель (аккумулятор). Вместо того чтобы достраивать результат «на обратном пути» из рекурсии, мы тащим частичный результат вперёд через дополнительный параметр. Это и аккуратнее, и — что критично — превращает рекурсию в хвостовую.

;; Без накопителя: сложение происходит ПОСЛЕ рекурсивного вызова
(defun sum-naive (lst)
  (if (null lst) 0
      (+ (first lst) (sum-naive (rest lst)))))   ; не хвостовая!

;; С накопителем: вызов self — последнее действие
(defun sum-acc (lst &optional (acc 0))
  (if (null lst) acc
      (sum-acc (rest lst) (+ acc (first lst)))))  ; хвостовая

(sum-acc '(1 2 3 4 5))   ; => 15

Разница тонкая, но принципиальная. В sum-naive после возврата из (sum-naive (rest lst)) нужно ещё прибавить (first lst) — значит, кадр стека обязан дождаться результата. В sum-acc результат рекурсивного вызова и есть результат функции — добавлять нечего. Это и есть хвостовой вызов.

Что такое хвостовая рекурсия и зачем она

Вызов называется хвостовым, если он стоит в «хвостовой позиции» — то есть его значение немедленно возвращается из текущей функции, без дальнейших операций над ним. Если каждый рекурсивный вызов хвостовой, рекурсия называется хвостовой. Её ценность в том, что текущий кадр стека больше не нужен в момент вызова: его можно переиспользовать. Реализация, выполняющая такую оптимизацию, превращает хвостовую рекурсию в обычный цикл, работающий в постоянной памяти. Это называется оптимизацией хвостового вызова (Tail Call Optimization, TCO), или, точнее, «properly tail-recursive» реализацией.

Где именно «хвостовая позиция»? В теле defun — последняя форма. В if — обе ветви (но не тест). В progn/when — последняя форма. В cond — тело каждой ветви. А вот аргумент функции — не хвостовая позиция: в (+ 1 (f x)) вызов (f x) не хвостовой, потому что над его результатом ещё выполнят сложение.

Scheme: TCO гарантирован стандартом

Здесь проходит важнейшая разделительная линия между диалектами. В Scheme правильная хвостовая рекурсия — обязательное требование стандарта (R5RS/R7RS). Любая корректная реализация Scheme обязана исполнять хвостовые вызовы в постоянном пространстве стека. Поэтому в Scheme рекурсия — это полноценная, безопасная замена циклам: можно писать бесконечные циклы как хвостовую рекурсию, и стек не переполнится никогда. Это краеугольный камень философии Scheme: дать минимальный набор примитивов, но гарантировать, что рекурсия из них масштабируется.

;; Scheme: хвостовая рекурсия гарантированно не растит стек
(define (sum-acc lst acc)
  (if (null? lst)
      acc
      (sum-acc (cdr lst) (+ acc (car lst)))))

(sum-acc '(1 2 3 4 5) 0)   ; => 15, работает и для миллиона элементов

;; named let — идиоматичный цикл Scheme на хвостовой рекурсии
(define (sum lst)
  (let loop ((xs lst) (acc 0))      ; loop — имя локальной рекурсии
    (if (null? xs)
        acc
        (loop (cdr xs) (+ acc (car xs))))))

Конструкция named let (именованный let) — фирменная идиома Scheme: вы заводите локальную рекурсивную функцию loop и сразу её запускаете. Это «цикл» Scheme, и благодаря гарантированному TCO он эквивалентен обычному циклу по эффективности. В Common Lisp прямого named let нет (его эмулируют через labels или просто пишут do/loop).

Стоит прочувствовать, насколько глубоко это меняет стиль. В Scheme нет нужды в отдельном «синтаксисе цикла» как в большинстве языков, потому что named let покрывает все случаи: счётный цикл — это рекурсия по счётчику, обход коллекции — рекурсия по хвосту, цикл «пока условие» — рекурсия с проверкой в базе. Один приём, выводимый из самой природы языка, заменяет for, while, foreach разом. Это и есть минимализм Scheme в действии: не добавлять конструкцию, если её можно выразить из имеющихся примитивов с той же эффективностью. Для человека, привыкшего к разнообразию циклов в мейнстриме, это поначалу непривычно, но затем открывается элегантность: меньше специальных правил — меньше того, что нужно держать в голове.

Common Lisp: TCO не гарантирован стандартом

А вот в Common Lisp стандарт ANSI не требует оптимизации хвостовых вызовов. Это сознательное решение: стандарт не хотел навязывать реализациям модель исполнения и хотел сохранить точные трассировки стека для отладки. Практическое следствие: нельзя полагаться на то, что глубокая хвостовая рекурсия не переполнит стек в переносимом коде. На практике большинство хороших реализаций (SBCL, CCL) умеют делать TCO — но часто только при достаточном уровне оптимизации компилятора, который надо включить декларацией.

;; SBCL обычно делает TCO при высокой оптимизации скорости:
(defun count-down (n)
  (declare (optimize (speed 3) (debug 0)))   ; просим скорость, не отладку
  (if (zerop n)
      'done
      (count-down (1- n))))                   ; хвостовой вызов

(count-down 10000000)   ; на SBCL отработает без переполнения стека

Но идиоматичный Common Lisp в таких случаях обычно не полагается на TCO, а пишет явный цикл — do, dotimes, dolist или loop. Это культурное различие диалектов: Scheme говорит «рекурсия — это и есть итерация», Common Lisp говорит «есть рекурсия и есть отдельные итеративные конструкции, выбирай по ситуации». Для обхода списков и деревьев в CL рекурсия прекрасна; для счётных циклов «сделай N раз» идиоматичнее dotimes.

Стоит понять, почему комитет ANSI сознательно не стал требовать TCO, — это поучительная история про инженерные компромиссы. Во-первых, обязательный TCO ограничивает реализацию: он по сути диктует модель компиляции вызовов, а Common Lisp хотел дать свободу авторам компиляторов (включая трансляцию в C, в байткод, в нативный код). Во-вторых — и это важнее — раскрутка кадров полезна для отладки: полный стек вызовов показывает, «как мы сюда попали». Агрессивный TCO стирает промежуточные кадры, и трассировка становится беднее. Common Lisp традиционно ценит интерактивную отладку (мы увидим это в разделе про условия), поэтому компромисс «не навязывать TCO» вписан в его философию. Scheme же выбрал противоположный приоритет: математическую чистоту, где рекурсия обязана масштабироваться, даже ценой отладочного удобства. Ни один выбор не «правильнее» — они отражают разные ценности языков.

Как работает под капотом

Когда вызывается функция, в стеке создаётся кадр (activation record): он хранит аргументы, локальные переменные и «куда вернуться». В обычной рекурсии кадры накапливаются, потому что каждый ждёт результата вложенного вызова, чтобы доделать своё. Это и ограничивает глубину: стек конечен, и тысячи-десятки тысяч кадров его исчерпают (знаменитое «stack overflow»). При хвостовом вызове доделывать нечего — текущий кадр можно выбросить до входа в вызываемую функцию. TCO ровно это и делает: заменяет «вызвать и вернуться» на «подготовить аргументы и перейти» (как goto), переиспользуя один кадр. Поэтому хвостовая рекурсия с TCO исполняется в O(1) по памяти стека — ровно как цикл. Без TCO та же рекурсия — O(n) по стеку и при большом n падает.

Частые ошибки

Считать любую рекурсию хвостовой. (+ x (f ...)) и (cons x (f ...)) — НЕ хвостовые: над результатом ещё работают. Хвостовой вызов — последнее действие без обёртки.
Полагаться на TCO в переносимом Common Lisp. Стандарт его не гарантирует. Для глубоких циклов в CL берите do/dotimes/loop либо явно включайте оптимизацию и проверяйте свою реализацию.
Забыть базовый случай. Рекурсия без условия остановки или без сведения к меньшей задаче не завершится — переполнение стека (в CL) или зависание.
Наивная древовидная рекурсия. Прямой рекурсивный Фибоначчи экспоненциален. Используйте накопители/мемоизацию, когда подзадачи повторяются.
Думать, что named let есть в Common Lisp. Это идиома Scheme. В CL аналог — локальная функция через labels или штатные циклы.

Итоги

Рекурсия в Lisp естественна: список — рекурсивная структура, обход повторяет его форму.
Каркас рекурсии: база (остановка) + шаг (сведение к меньшему).
Накопитель тащит частичный результат вперёд и превращает рекурсию в хвостовую.
Хвостовой вызов — последнее действие функции; с TCO исполняется в постоянной памяти стека.
Scheme гарантирует TCO стандартом (named let — идиоматичный цикл); Common Lisp — нет.
В переносимом CL для глубоких циклов берут явную итерацию, а не надеются на TCO.