Практика преподавания и изучения программирования преимущественно на базе императивных языков (включая объектно-ориентированные императивные языки) приводит к тому, что такой фундаментальный алгоритмический механизм, как рекурсия, остаётся плохо понятным многими программистами и порождает заблуждения, транслируемые в популярной культуре. Попытаемся внести в вопрос немного ясности и изложить некоторые свои мысли по этому поводу.
Что такое рекурсия?
Что такое рекурсия в бытовом понимании? Это решение задачи через сведение её к самой себе в более простых условиях.
Допустим, мы туристы, и перед нами стоит задача попытаться найти в доставшемся нам рюкзаке с едой банку тушёнки. Проверим, пустой ли рюкзак. Если пустой, задача решена, тушёнки нет. Иначе вынимаем из рюкзака первый попавшийся предмет. Если это банка тушёнки, задача решена, тушёнка найдена. Иначе повторяем весь наш алгоритм для имеющегося теперь у нас полегчавшего рюкзака с оставшимся содержимым, и результат решения задачи при этом откладывается на следующий шаг.
Этот пример рекурсии поймёт и маленький ребёнок, а программисты заметят, что это по существу задача поиска элемента в односвязном списке.
Рекурсия сама по себе представляет просто один из возможных способов описания повторяющихся действий. Цикл всегда может быть описан в виде рекурсии. Рекурсия может быть описана в виде конечного числа циклов, но это иногда может потребовать дополнительной структуры данных, хранящей последовательность рекурсивных вызовов.
Определения
Формально введём некоторые определения. Вопрос далеко не нов, поэтому возьмём определения из достаточно академичных источников, таких как [Friedman1975] и [Хювёнен1990]. В математике рекурсия рассматривается в теории рекурсивных функций, являющейся одним из формализмов теории алгоритмов, поэтому определения многих терминов имеют базу в виде очень чётко заданных математических понятий.
Рекурсия – использование самого себя. Также для простоты словом рекурсия называют рекурсивный вызов.
Рекурсивный вызов – прямой или опосредованный вызов функцией самой себя.
Простая рекурсия – рекурсивный вызов, встречающийся не более одного раза в каждой ветви кода функции. Чандра в [Chandra1972] показал, что простая рекурсия всегда может быть сведена компилятором к итеративному циклу, в дальнейшем этот результат был улучшен, что описано ниже.
Терминальная ветвь – ветвь кода рекурсивной функции, завершающая его без дальнейших рекурсивных вызовов.
Бесконечная рекурсия – последовательность рекурсивных вызовов, неограниченное число раз выполняющая новые рекурсивные вызовы. Обратите внимание, что не любой бесконечно выполняющийся рекурсивный алгоритм является бесконечной рекурсией (контрпримером является бесконечный нерекурсивный цикл на одном из этапов рекурсивного алгоритма).
Параллельная рекурсия – рекурсия, встречающаяся несколько раз в одной ветви кода функции.
Взаимная рекурсия – вызов двумя или более функциями друг друга.
Рекурсия по значению – рекурсивный вызов, определяющий результат функции.
Рекурсия по аргументам – рекурсивный вызов, участвующий в вычислении аргументов функции.
Рекурсия высокого порядка – случай, когда в определении функции рекурсивный вызов является аргументом вызова этой же самой функции. Обратите внимание, что рекурсия высокого порядка не имеет никакого отношения к функциям высокого порядка. При помощи рекурсии порядка N могут быть описаны вычисления в N+1 вложенных циклах, однако обратное не всегда верно.
Порядок рекурсии – уровень, на котором находится вызов в рекурсии высокого порядка. Обычные используемые на практике случаи рекурсии содержат рекурсивные вызовы нулевого порядка.
Стилизованная рекурсивная функция – некий специальный вид рекурсивной функции нулевого порядка, более общий, чем простая рекурсия, и удовлетворяющий семи довольно замысловато сформулированным требованиям, описанным в статье [Friedman1975] (желающие могут прочитать их по ссылке ниже, страницы 4-5 статьи). Авторы показывают, что стилизованная рекурсивная функция всегда может быть сведена компилятором к итеративному циклу.
Далее приведены строго не определённые понятия.
Хвостовая рекурсия – простая рекурсия, рекурсивный вызов в которой находится в конце кода функции. Многие источники в интернете называют хвостовой рекурсией только такие вызовы, которые непосредственно предшествуют возврату из функции (назовём это хвостовой рекурсией I), в то время как другие интерпретируют хвостовую рекурсию более широко, понимая её как однократный рекурсивный вызов где-либо в последней линейной ветке кода (назовём это хвостовой рекурсией II), или как простую рекурсию. По любому определению, хвостовая рекурсия является частным случаем простой рекурсии.
Оптимизация хвостовой рекурсии, или оптимизация хвостового вызова – преобразование транслятором хвостового вызова функции (необязательно рекурсивного) в линейный (циклический) код. Здесь опять-таки широк диапазон интерпретаций, начиная от простой замены пары команд call/ret на jmp (которая в том числе устраняет хвостовую рекурсию I) и заканчивая более сложными оптимизациями хвостовой рекурсии II и простой рекурсии.
Применение определений
Наш бытовой пример с тушёнкой в рюкзаке представлял собой простую рекурсию с двумя терминальными ветвями и хвостовой рекурсией. Заметим, что рекурсивный код всегда начинается с терминальных ветвей, иначе исполнение программы погрузится в бесконечную рекурсию и никогда до них не дойдёт.
Напишем псевдокод на языке Лисп для наших туристов, чтобы они точно понимали, что делать, проснувшись утром голодными и не помнящими, что у них в рюкзаках:
(defun ищемТушёнку (рюкзак)
(cond
((null рюкзак) nil)
((тушёнка? (car рюкзак)) (car рюкзак))
(t (ищемТушёнку (cdr рюкзак)))))
Здесь мы определили функцию ищемТушёнку от параметра-списка рюкзак. Её тело состоит из условного оператора cond, имеющего две терминальные и одну рекурсивную ветку. Рюкзак проверяется на пустоту, затем первый элемент рюкзака (car рюкзак) проверяется специальным предикатом, не тушёнка ли это, затем по третьей ветви, которая предваряется тождественно истинным к этому моменту условием t, уходим на рекурсивный вызов с остатком списка (cdr рюкзак).
Если есть желание довести дело до компьютерного исполняемого кода, определим также наш предикат:
(defun тушёнка? (x) (eq x 'тушёнка))
Прямо в таком виде это можно ввести в GNU Common Lisp или SBCL и искать тушёнку.
(ищемТушёнку '(носки хлеб учебникЛиспа штопор
тушёнка смартфон ноутбук
шишка шишка кирпич носовойПлаток
нож кредитка конфета бумажка
зубочистка непонятныйМусор))
ТУШЁНКА
Код здесь написан в чисто функциональном стиле, не содержит переменных и присваиваний, что эффективно с точки зрения распределения памяти в статической секции и в куче.
Эффективность рекурсии
Многие программисты считают, что рекурсия неэффективна, так как поедает место на стеке, и ей не место в продуктовом коде. Так ли это?
Безусловно, всякий инструмент нужно применять по назначению, и для перебора чисел от 1 до N, наверное, не надо использовать рекурсивный вызов. Тем не менее, так ли ужаcна рекурсия по сравнению с итерированным циклом?
Современные 64-разрядные системы программирования обычно без труда позволяют распределять до гигабайтов адресного пространства в стековой памяти. Этого хватит буквально на миллиарды вложенных рекурсивных вызовов. Вряд ли когда-нибудь вам понадобится рекурсия такой глубины, и даже если да, то основной проблемой, скорее всего, станет процессорное время, а не стековая память. Цикл с содержательным смыслом на миллиард итераций – это дело серьёзное. Тем не менее, проблема со стеком всё-таки есть, и о ней необходимо помнить.
Однако, как следует из приводившихся выше определений, всякая стилизованная рекурсия и тем более всякая простая рекурсия приводима к виду итеративного цикла. Многие трансляторы об этом знают, в большем или меньшем объёме.
Часто использующимся в компиляторах приёмом оптимизации является оптимизация хвостовой рекурсии, или tail call (tail recursion) optimization. Многим программистам известно, что обычно трансляторы преобразуют хвостовую рекурсию I в эквивалентный цикл, поэтому такая задача, как наш поиск в рюкзаке, после оптимизации не будет занимать место на стеке по мере продвижения в глубины рюкзака.
Однако, интернет полон мнений, что способность компилятора к оптимизации хвостовой рекурсии исчерпывается заменой пары команд call/ret на команду jmp. Поэтому, якобы, даже обычная функция факториала в виде
(defun fact (n)
(cond
((zerop n) 1)
(t (* n (fact (- n 1))))))
непригодна к оптимизации и вызовет разрушительный рост стека, так как после рекурсивного вызова остаётся выполнить ещё умножение, и код функции, таким образом, не представляет собой хвостовую рекурсию I. Дальше разделяющие такое мнение люди предлагают "оптимизировать" этот факториал, передавая умножаемые значения вторым параметром.
В действительности, например, у [Penman2018] разобран пример компиляции соответствующего кода в C/C++ и показано, что хвостовая рекурсия II оптимизируется и заменяется на цикл современным компилятором. Попытки выполнить такую оптимизацию вручную ни к чему не приводят на уровне машинного кода и только затрудняют понимание исходного текста.
В общем-то, уже на уровне здравого смысла понятно, что вычисления, записанные в коде после вызова хвостовой рекурсии II, можно переместить из эпилога получаемого цикла в пролог его следующей итерации, чем свести задачу к хвостовой рекурсии I.
На практике оказывается, что компиляторы популярных для вычислений языков (Си/Си++, Фортран) как правило, обеспечивают глубокую оптимизацию хвостовой рекурсии при включённой оптимизации. Трансляторы Лиспа оптимизируют хвостовую рекурсию в разной степени. Трансляторы Джавы и Питона не оптимизирует хвостовую рекурсию по принципиальным соображениям, так как разработчики считают важным сохранять исходную трассировку вызовов.
Оптимизация некоторых рекурсивных вычислительных процессов также может может быть достигнута путём применения механизма мемоизации.
Наконец, вновь надо вернуться к обстоятельству, что уже значение (fact 1000) занимает целый экран цифрами получившегося числа, а в стеке набирается всего 1000 элементов.
Кошмары высокого порядка
Рассмотрим теперь действительно не оптимизируемую автоматически рекурсивную функцию, например, крайне вычислительно ёмкую функцию Аккермана с рекурсией первого порядка, быстро уходящей на огромную глубину. Цитируется по [Хювяйнен1990]:
(defun аккерман (m n)
(cond
((= m 0) (+ n 1))
((= n 0) (аккерман (- m 1) 1))
(t (аккерман (- m 1) (аккерман m (- n 1))))))
Значение (аккерман 4 1) считается на компьютере автора в SBCL за 16 секунд с занятым стеком менее 4 мегабайт, то есть стек расходуется со скоростью 256 килобайт в секунду. Таким образом, 4-гигабайтного стека хватило бы на 4.5 часа вычислений рекурсивной функции, ничего по существу не делающей, кроме углубления своей рекурсии. (Для завершённости заметим, что значение (аккерман 4 2) вычислить брутфорсом через её рекурсивное определение пока не в человеческих силах, хотя имеется более быстрый альтернативный алгоритм [Grossman1988]; и полагаем совершенно невероятным, чтобы кому-либо в практических целях понадобился вычислительный процесс, описываемый рекурсией второго и более порядка).
Вывод
Так как это статья о рекурсии, то вывод заключается в том, что выводы представлены в самой этой статье о рекурсии.
Литература
[Хювёнен1990] Э. Хювёнен, Й. Сеппянен. Мир Лиспа. М.: Мир, 1990.
[Chandra1972] A. Chandra. Efficient compilation of linear recursive programs. Stanford AI project, STAN‑CS-72–282, 1972.