Рекурсия: loop, recur и почему нет хвостовых вызовов

Главная мысль урока: каждый рекурсивный вызов в Clojure занимает место на стеке, и язык не убирает его даже в хвостовой позиции. Поэтому для длинных повторений есть recur: явный прыжок в начало loop или функции, который стек не расходует, а компилятор проверяет, что прыжок стоит на своём месте.

Помнишь бесконечное подземелье из урока про лень? Герой спускается с этажа на этаж, и мы хотим знать, сколько этажей под ним. Рекурсивное определение напрашивается само: если этажей ноль, ответ ноль; иначе один этаж плюс все этажи ниже.

Красиво и правильно. Теперь возьмём подземелье поглубже:

Куда делся стек

Каждый вызов функции получает кадр стека: место под аргументы и адрес возврата. (floors-below 100000) не может вернуть ответ, пока не узнает (floors-below 99999), тот ждёт 99998, и так сто тысяч кадров один на другом. Стек ограничен, обычно его хватает на несколько тысяч или десятков тысяч вызовов, дальше программа падает. В браузере это Maximum call stack size exceeded, на JVM StackOverflowError:

(defn floors-below [n]
  (if (zero? n)
    0
    (inc (floors-below (dec n)))))

(println (floors-below 1000))
(def result
  (try (floors-below 1000000)
       (catch StackOverflowError _ :stack-overflow)))
(println result)
(assert (= :stack-overflow result))

Если ты проходил рекурсию в JavaScript, картина знакома.

В Haskell или Scheme такую функцию переписали бы так, чтобы рекурсивный вызов стоял последним, и компилятор сам превратил бы его в прыжок. Такой вызов называют хвостовым: после него функции нечего досчитывать, поэтому её кадр можно выбросить. В floors-below вызов не хвостовой, после него ещё работает inc.

Clojure хвостовые вызовы не оптимизирует. Причина в хосте: JVM не даёт инструмента выбросить кадр текущего метода при вызове другого, а Clojure компилирует функции в обычные методы JVM. Рич Хики выбрал честность: вместо оптимизации, которая то срабатывает, то нет, язык даёт явную форму recur.

loop и recur

Перепишем подсчёт так, чтобы ничего не ждать после вызова. Для этого нужен аккумулятор: аргумент, который несёт посчитанное до сих пор. А вместо вызова самой себя функция делает recur:

Миллион этажей, и стек цел. Разберём по шагам:

1. loop заводит локальные имена left и counted с начальными значениями, как let.
2. Тело проверяет условие выхода. Если этажи кончились, возвращает counted.
3. Иначе recur прыгает в начало loop с новыми значениями: left на единицу меньше, counted на единицу больше.
4. Прыжок не создаёт кадр, это цикл в одном вызове. Аргументов у recur ровно столько, сколько имён в loop.

recur работает и без loop, тогда он прыгает в начало самой функции, а новые значения получают её параметры:

Похожий приём разбирали в уроке про Janet, только там цикл loop устроен иначе, а хвостовые вызовы Janet оптимизирует сама.

recur обязан стоять в хвосте

recur нельзя поставить где угодно. Он должен быть последним действием в своей ветке, то есть в хвостовой позиции: последняя форма тела, ветка if, cond или case, тело let. Попытка обернуть recur во что-то ещё, например (inc (recur ...)), на JVM не скомпилируется. Компилятор Clojure откажется с ошибкой Can only recur from tail position.

Это важная гарантия. В языках с автоматической оптимизацией легко случайно сломать хвостовой вызов, дописав одно inc, и узнать об этом от игроков, на большом входе. В Clojure ошибку покажет компилятор ещё до запуска: либо прыжок на своём месте, либо код не собирается.

Одна оговорка про песочницу. SCI и babashka это интерпретаторы, и они такую проверку не делают: (fn [x] (inc (recur x))) в браузере создастся без ошибки. Проверяет только настоящий компилятор на JVM, поэтому код с recur не в хвосте может пройти здесь, а упасть в проекте.

Взаимная рекурсия и trampoline

recur прыгает только в свою функцию. А если функций две, и они вызывают друг друга? В игре герой спускается по лестнице: на чётном шаге лестница, на нечётном площадка, и каждая знает только о соседе.

Хитрость в том, что stairs и landing не вызывают друг друга, а возвращают функцию без аргументов, которая сделает следующий шаг: #(landing (dec n)). trampoline вызывает функцию, смотрит на результат: если это снова функция, вызывает её, и так пока не получит обычное значение. Стек не растёт, потому что каждый шаг возвращается в trampoline, прежде чем начнётся следующий. declare нужен, чтобы stairs могла сослаться на landing до её определения.

Если конечный результат сам функция, trampoline попытается её вызвать. Такой ответ заверни в мапу или вектор.

Когда рекурсия вовсе не нужна

Большинство циклов над данными в Clojure пишут вообще без рекурсии. Сравни:

Сумма это reduce, «сколько ходов до полного здоровья» это iterate и take-while, поиск первого подходящего это some. Функции из урока про библиотеку последовательностей короче, и в них нет места для ошибки в условии выхода. Правило выбора:

Задача	Что брать
Свернуть, отобрать, преобразовать коллекцию	reduce, filter, map
Цикл с несколькими меняющимися значениями и сложным выходом	loop и recur
Обход дерева неглубокой вложенности	обычная рекурсия или tree-seq
Две функции, которые передают ход друг другу	trampoline

Обычная рекурсия не запрещена. Дерево сундуков, где в сундуке лежат сундуки, вряд ли будет глубже десяти уровней, и рекурсивная функция для него читается лучше любого цикла. Опасна рекурсия, глубина которой растёт вместе с размером входа: длина пути, число ходов, количество событий в логе.

Попробуй руками

В задаче три функции. Проход по подземелью до выхода с защитой от циклов и подсчёт ходов регенерации требуют loop и recur: тесты гоняют их на десяти тысячах комнат и пятидесяти тысячах ходов. Золото во вложенных сундуках посчитай обычной рекурсией.

Проверь себя

Задание

Дальше

Функциональное ядро позади: функции, лень, библиотека последовательностей, конвейеры и циклы без изменяемых переменных. Но игра должна где-то хранить мир, который меняется каждый ход. В следующем уроке разберём, как Clojure разделяет неизменяемые значения и меняющиеся во времени ссылки.