Введение

Использование функций, вызывающих самих себя

В информатике рекурсия — это метод решения вычислительной задачи, в котором решение зависит от решений меньших экземпляров той же задачи. Рекурсия решает такие рекурсивные задачи, используя функции, которые вызывают себя изнутри своего собственного кода. Этот подход может быть применен ко многим типам задач, и рекурсия является одной из центральных идей информатики. Большинство языков программирования поддерживают рекурсию, позволяя функции вызывать себя изнутри своего кода. Некоторые функциональные языки программирования (например, Clojure) не определяют никаких циклов, а полагаются исключительно на рекурсию для повторного вызова кода. В теории вычислимости доказано, что эти рекурсивные языки являются полными по Тьюрингу; это означает, что они столь же мощны (могут использоваться для решения тех же задач), как и императивные языки, основанные на управляющих структурах, таких как и . Повторный вызов функции изнутри себя может привести к тому, что размер стека вызовов будет равен сумме размеров входных данных всех участвующих вызовов. Следовательно, для задач, которые можно легко решить итерацией, рекурсия обычно менее эффективна, а для определенных задач алгоритмические или компиляторные методы оптимизации, такие как оптимизация хвостовой рекурсии, могут повысить вычислительную производительность по сравнению с наивной рекурсивной реализацией.

Рекурсивные функции и алгоритмы

Обычная тактика разработки алгоритма состоит в том, чтобы разделить проблему на подзадачи того же типа, что и исходная, решить эти подзадачи и объединить результаты. Это часто называют методом "разделяй и властвуй"; при сочетании с таблицей поиска, хранящей результаты ранее решенных подзадач (для избежания повторных вычислений и дополнительных затрат времени), это можно назвать динамическим программированием или мемоизацией.

Базовый случай

Определение рекурсивной функции имеет один или несколько базовых случаев, то есть входные данные, для которых функция выдает результат тривиально (без рекурсии), и один или несколько рекурсивных случаев, то есть входные данные, для которых программа осуществляет рекурсию (вызывает саму себя). Например, факториальная функция может быть определена рекурсивно уравнениями 1 = 0! = 1 и для всех n > 0, 1 = n! = n * (n − 1)!. Ни одно из уравнений само по себе не является полным определением; первое – это базовый случай, а второе – рекурсивный случай. Поскольку базовый случай прерывает цепочку рекурсии, его иногда также называют "случаем завершения". Задача рекурсивных случаев состоит в том, чтобы разбить сложные входные данные на более простые. В правильно спроектированной рекурсивной функции с каждым рекурсивным вызовом входная задача должна упрощаться таким образом, чтобы в конечном итоге был достигнут базовый случай. (Функции, которые не предназначены для завершения в нормальных условиях – например, некоторые системные и серверные процессы – являются исключением из этого правила). Отсутствие базового случая или его неправильная проверка может привести к бесконечному циклу. Для некоторых функций (например, вычисляющей ряд для 1/e (математической константы)) нет очевидного базового случая, вытекающего из входных данных; для таких функций можно добавить параметр (например, количество слагаемых в нашем примере ряда), чтобы предоставить "критерий остановки", который устанавливает базовый случай. Такой пример естественнее рассматривать с помощью корекурсии, где последовательные элементы вывода являются частичными суммами; это можно преобразовать в рекурсию, используя параметр индексации, чтобы указать "вычислить n-й элемент (n-ю частичную сумму)".

Рекурсивные типы данных

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

Однократная рекурсия и многократная рекурсия

Рекурсия, содержащая только одну самоссылку, называется одинарной рекурсией, а рекурсия, содержащая несколько самоссылок, называется множественной рекурсией. Типичные примеры одинарной рекурсии включают обход списка, например, при линейном поиске, или вычисление факториала, в то время как типичные примеры множественной рекурсии включают обход дерева, например, при поиске в глубину. Одинарная рекурсия часто гораздо эффективнее множественной рекурсии и, как правило, может быть заменена итеративным вычислением, выполняемым за линейное время и требующим постоянного объема памяти. Множественная рекурсия, напротив, может потребовать экспоненциального времени и памяти и является более фундаментально рекурсивной, не поддающейся замене итерацией без использования явного стека. Множественную рекурсию иногда можно преобразовать в одинарную рекурсию (а при желании – и в итерацию). Например, хотя наивное вычисление последовательности Фибоначчи подразумевает множественную рекурсию, поскольку каждое значение требует двух предыдущих, его можно вычислить с помощью одинарной рекурсии, передавая два последовательных значения в качестве параметров. Это естественнее рассматривать как корекурсию, строящуюся от начальных значений, при этом отслеживаются два последовательных значения на каждом шаге – см. Корекурсия: примеры. Более сложный пример – использование нитевого двоичного дерева, которое позволяет итеративно обходить дерево, а не использовать множественную рекурсию.

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

Большинство основных примеров рекурсии, и большинство примеров, представленных здесь, демонстрируют прямую рекурсию, в которой функция вызывает саму себя. Косвенная рекурсия возникает, когда функция вызывается не напрямую собой, а другой функцией, которую она ранее вызвала (непосредственно или косвенно). Например, если функция f вызывает функцию f, это прямая рекурсия, но если функция f вызывает функцию g, которая, в свою очередь, вызывает функцию f, то это косвенная рекурсия функции f. Возможны цепочки из трех и более функций; например, функция 1 вызывает функцию 2, функция 2 вызывает функцию 3, а функция 3 снова вызывает функцию 1. Косвенная рекурсия также называется взаимной рекурсией, что является более симметричным термином, хотя это лишь разница в акценте, а не иное понятие. То есть, если функция f вызывает функцию g, а затем функция g вызывает функцию f, которая, в свою очередь, снова вызывает функцию g, то с точки зрения только функции f она косвенно рекурсирует, а с точки зрения только функции g – она также косвенно рекурсирует, в то время как с точки зрения обеих функций f и g они взаимно рекурсируют друг на друга. Аналогично, набор из трех или более функций, которые вызывают друг друга, можно назвать набором взаимно рекурсивных функций.

Анонимная рекурсия

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

Функция обертыва

Функция-обертка — это функция, которая вызывается непосредственно, но не рекурсирует сама по себе, а вместо этого вызывает отдельную вспомогательную функцию, которая и выполняет рекурсию. Функции-обертки могут использоваться для проверки параметров (чтобы рекурсивная функция могла пропускать эти проверки), выполнения инициализации (выделения памяти, инициализации переменных), особенно для вспомогательных переменных, таких как «уровень рекурсии» или частичные вычисления для мемоизации, а также для обработки исключений и ошибок. В языках, поддерживающих вложенные функции, вспомогательная функция может быть вложена внутрь функции-обертки и использовать общую область видимости. Если вложенные функции недоступны, вспомогательные функции реализуются как отдельные функции, по возможности приватные (поскольку они не вызываются напрямую), а информация передается функции-обертке посредством передачи по ссылке.

Гибридный алгоритм

Рекурсивные алгоритмы часто неэффективны для небольших объемов данных из-за накладных расходов, связанных с многократными вызовами и возвратами функций. По этой причине эффективные реализации рекурсивных алгоритмов часто начинаются с рекурсивного алгоритма, но затем переключаются на другой алгоритм, когда размер входных данных становится небольшим. Важным примером является сортировка слиянием, которая часто реализуется путем перехода к нерекурсивной сортировке вставками, когда объем данных достаточно мал, как, например, в сортировке слиянием с разбиением на блоки. Гибридные рекурсивные алгоритмы часто можно дополнительно оптимизировать, как в случае Timsort, который основан на гибридной сортировке слиянием/вставками.

Выразительная сила

Большинство языков программирования, используемых сегодня, позволяют напрямую задавать рекурсивные функции и процедуры. При вызове такой функции среда выполнения программы отслеживает различные экземпляры этой функции (часто с использованием стека вызовов, хотя могут применяться и другие методы). Любую рекурсивную функцию можно преобразовать в итеративную, заменяя рекурсивные вызовы итеративными конструкциями управления и эмулируя стек вызовов с помощью стека, явно управляемого программой. Обратно, все итеративные функции и процедуры, которые могут быть вычислены компьютером (см. полноту по Тьюрингу), могут быть выражены через рекурсивные функции; итеративные конструкции управления, такие как циклы while и for, обычно переписываются в рекурсивной форме в функциональных языках. Однако на практике такая перепись зависит от оптимизации хвостовой рекурсии, которая не поддерживается во всех языках. C, Java и Python – известные широко используемые языки, в которых все вызовы функций, включая хвостовые вызовы, могут приводить к выделению памяти в стеке, что не происходит при использовании циклов; в этих языках рабочая итеративная программа, переписанная в рекурсивной форме, может вызвать переполнение стека, хотя оптимизация хвостовой рекурсии может быть реализована, но не определена спецификацией языка, и различные реализации одного и того же языка могут различаться по своим возможностям оптимизации хвостовой рекурсии.

Проблемы с производительностью

В языках (таких как C и Java), которые отдают предпочтение итеративным циклам, рекурсивные программы обычно связаны со значительными затратами времени и памяти из-за накладных расходов на управление стеком и относительной медлительности вызовов функций. В функциональных языках вызов функции (особенно хвостовой вызов) обычно выполняется очень быстро, и эта разница менее заметна. Например, разница в производительности между рекурсивной и итеративной реализациями примера с "факториалом", приведенного выше, сильно зависит от используемого компилятора. В языках, где предпочтительны циклы, итеративная версия может быть на несколько порядков быстрее рекурсивной. В функциональных языках общая разница во времени выполнения между двумя реализациями может быть пренебрежимо мала; более того, затраты на умножение больших чисел раньше меньших (что происходит в представленной здесь итеративной версии) могут нивелировать любую экономию времени, достигаемую за счет использования итерации.

Пространство стека

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

Уязвимость

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

Умножение рекурсивных задач

Многократно рекурсивные задачи по своей природе рекурсивны из-за необходимости отслеживать предыдущее состояние. Примером может служить обход дерева, как при поиске в глубину; хотя используются как рекурсивные, так и итеративные методы, они отличаются от обхода списка и линейного поиска в списке, который является однократно рекурсивным и, следовательно, естественно итеративным. Другие примеры включают алгоритмы типа "разделяй и властвуй", такие как Quicksort, и функции, такие как функция Аккермана. Все эти алгоритмы можно реализовать итеративно с использованием явного стека, но усилия программиста, затрачиваемые на управление стеком, и сложность результирующей программы, вероятно, перевешивают любые преимущества итеративного решения.

Рефакторинг рекурсии

Рекурсивные алгоритмы могут быть заменены на нерекурсивные аналоги. Один из способов замены рекурсивных алгоритмов — имитация их работы с использованием кучи вместо стека. Альтернативный подход — разработка алгоритма, полностью основанного на нерекурсивных методах, что может быть непростой задачей. Например, рекурсивные алгоритмы для сопоставления подстановочных знаков, такие как алгоритм wildmat, разработанный Ричем Салцем, ранее часто использовались. Нерекурсивные алгоритмы для той же цели, например, алгоритм сопоставления подстановочных знаков Крауса, были разработаны для устранения недостатков рекурсии и улучшались постепенно, благодаря таким методам, как сбор тестовых примеров и профилирование производительности.