Рекурсия (информатика)

Дерево, созданное с использованием языка программирования Logo и в значительной степени опирающееся на рекурсию. Каждую ветвь можно рассматривать как уменьшенную версию дерева.

В информатике рекурсия — это метод решения вычислительной задачи , где решение зависит от решений меньших экземпляров той же задачи. ^[1]^[2] Рекурсия решает такие рекурсивные задачи с помощью функций , которые вызывают себя из своего собственного кода. Этот подход может быть применен ко многим типам задач, и рекурсия является одной из центральных идей информатики. ^[3]

Сила рекурсии, очевидно, заключается в возможности определения бесконечного множества объектов конечным оператором. Таким же образом бесконечное число вычислений может быть описано конечной рекурсивной программой, даже если эта программа не содержит явных повторений.
— Никлаус Вирт , Алгоритмы + Структуры данных = Программы , 1976 ^[4]

Большинство языков программирования поддерживают рекурсию, позволяя функции вызывать себя из собственного кода. Некоторые функциональные языки программирования (например, Clojure ) ^{[5] не определяют никаких циклических конструкций, а полагаются исключительно на рекурсию для многократного вызова кода. В}теории вычислимости доказано , что эти рекурсивно-полные языки являются полными по Тьюрингу ; это означает, что они столь же мощны (их можно использовать для решения тех же задач), как и императивные языки, основанные на управляющих структурах, таких как whileи for.

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

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

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

Базовый вариант

Определение рекурсивной функции имеет один или несколько базовых случаев , то есть входные данные, для которых функция выдает результат тривиально (без повторения), и один или несколько рекурсивных случаев , то есть входные данные, для которых программа рекурсивно (вызывает себя). Например, функция факториала может быть определена рекурсивно уравнениями $0! = 1$ и, для всех $n > 0$ , $n! = n (n - 1)!$ . Ни одно из уравнений само по себе не составляет полного определения; первое является базовым случаем, а второе — рекурсивным случаем. Поскольку базовый случай прерывает цепочку рекурсии, его иногда также называют «завершающим случаем».

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

Для некоторых функций (например, вычисляющих ряд для $e = 1/0! + 1/1! + 1/2! + 1/3! + ...$ ) нет очевидного базового случая, подразумеваемого входными данными; для них можно добавить параметр (например, количество членов, которые нужно добавить, в нашем примере ряда), чтобы обеспечить «критерий остановки», который устанавливает базовый случай. Такой пример более естественно обрабатывается с помощью корекурсии , ^{[ как? ]} , где последовательные члены в выходных данных являются частичными суммами; это можно преобразовать в рекурсию, используя параметр индексации, чтобы сказать «вычислить n- й член ( n -ю частичную сумму)».

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

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

Индуктивно определенные данные

Индуктивно определенное рекурсивное определение данных — это определение, которое указывает, как создавать экземпляры данных. Например, связанные списки могут быть определены индуктивно (здесь, с использованием синтаксиса Haskell ):

данные ListOfStrings = EmptyList | Cons String ListOfStrings

Код выше определяет список строк как пустой или как структуру, содержащую строку и список строк. Самоссылка в определении позволяет строить списки из любого (конечного) числа строк.

Другим примером индуктивного определения являются натуральные числа (или положительные целые числа ):

Натуральное число — это либо 1, либо n+1, где n — натуральное число.

Аналогично рекурсивные определения часто используются для моделирования структуры выражений и операторов в языках программирования. Разработчики языков часто выражают грамматики в синтаксисе, таком как форма Бэкуса–Наура ; вот такая грамматика для простого языка арифметических выражений с умножением и сложением:

 < выражение >  ::=  < число > | ( < выражение > * < выражение > ) | ( < выражение > + < выражение > )

Это говорит о том, что выражение является либо числом, либо произведением двух выражений, либо суммой двух выражений. Рекурсивно ссылаясь на выражения во второй и третьей строках, грамматика допускает произвольно сложные арифметические выражения, такие как (5 * ((3 * 6) + 8)), с более чем одной операцией произведения или суммы в одном выражении.

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

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

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

Поток строк — это объект, такой что: head(s) — это строка, и tail(s) — это поток строк.

Это очень похоже на индуктивное определение списков строк; разница в том, что это определение указывает, как получить доступ к содержимому структуры данных, а именно, через функции доступаhead и tail, и каким может быть это содержимое, тогда как индуктивное определение указывает, как создать структуру и из чего она может быть создана.

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

Типы рекурсии

Одиночная рекурсия и множественная рекурсия

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

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

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

Непрямая рекурсия

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

Косвенная рекурсия также называется взаимной рекурсией , что является более симметричным термином, хотя это просто разница в акцентах, а не другое понятие. То есть, если f вызывает g, а затем g вызывает f, который в свою очередь снова вызывает g , с точки зрения только f , f является косвенно рекурсивной, в то время как с точки зрения только g , она является косвенно рекурсивной, в то время как с точки зрения обоих, f и g являются взаимно рекурсивными друг на друга. Аналогично набор из трех или более функций, которые вызывают друг друга, можно назвать набором взаимно рекурсивных функций.

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

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

Структурная и генеративная рекурсия

Некоторые авторы классифицируют рекурсию как «структурную» или «генеративную». Различие связано с тем, откуда рекурсивная процедура получает данные, с которыми она работает, и как она обрабатывает эти данные:

[Функции, потребляющие структурированные данные] обычно разлагают свои аргументы на непосредственные структурные компоненты, а затем обрабатывают эти компоненты. Если один из непосредственных компонентов принадлежит к тому же классу данных, что и входные данные, функция является рекурсивной. По этой причине мы называем эти функции (СТРУКТУРНО) РЕКУРСИВНЫМИ ФУНКЦИЯМИ.
— Феллейзен, Финдлер, Флэтт и Кришнаурти, Как разрабатывать программы , 2001 ^[6]

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

Альтернативой является генеративная рекурсия :

Многие известные рекурсивные алгоритмы генерируют совершенно новый фрагмент данных из заданных данных и повторяются на нем. HtDP ( How to Design Programs ) называет этот тип генеративной рекурсией. Примерами генеративной рекурсии являются: gcd , quicksort , binary search , mergesort , Newton's method , fractals и adaptive integration .
— Маттиас Феллейзен, Расширенное функциональное программирование , 2002 ^[7]

Это различие важно для доказательства прекращения функции.

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

Проблемы внедрения

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

Функция оболочки (вверху)
Короткое замыкание базового случая, также известное как «рекурсия на расстоянии вытянутой руки» (внизу)
Гибридный алгоритм (внизу) — переключение на другой алгоритм, когда данных становится достаточно мало

На основе элегантности функции-обертки обычно одобряются, в то время как сокращение базового случая не приветствуется, особенно в академических кругах. Гибридные алгоритмы часто используются для эффективности, чтобы уменьшить накладные расходы рекурсии в небольших случаях, и рекурсия на расстоянии вытянутой руки является особым случаем этого.

Функция оболочки

Функция -обертка — это функция, которая вызывается напрямую, но не рекурсирует себя, а вместо этого вызывает отдельную вспомогательную функцию, которая фактически выполняет рекурсию.

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

Короткое замыкание базового варианта

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

Короткое замыкание в первую очередь вызывает беспокойство, когда встречается много базовых случаев, таких как указатели Null в дереве, которые могут быть линейными по количеству вызовов функций, следовательно, значительная экономия для алгоритмов $O (n)$ ; это проиллюстрировано ниже для поиска в глубину. Короткое замыкание на дереве соответствует рассмотрению листа (непустого узла без потомков) в качестве базового случая, а не пустого узла в качестве базового случая. Если есть только один базовый случай, например, при вычислении факториала, короткое замыкание обеспечивает только экономию $O (1) .$

Концептуально, можно считать, что короткое замыкание имеет либо тот же базовый случай и рекурсивный шаг, проверяя базовый случай только перед рекурсией, либо можно считать, что оно имеет другой базовый случай (на один шаг удаленный от стандартного базового случая) и более сложный рекурсивный шаг, а именно «проверить действительность, затем рекурсировать», как при рассмотрении листовых узлов, а не нулевых узлов в качестве базовых случаев в дереве. Поскольку короткое замыкание имеет более сложный поток по сравнению с четким разделением базового случая и рекурсивного шага в стандартной рекурсии, его часто считают плохим стилем, особенно в академических кругах. ^[8]

Поиск в глубину

Базовый пример короткого замыкания приведен в поиске в глубину (DFS) двоичного дерева; см. раздел «Двоичные деревья» для стандартного рекурсивного обсуждения.

Стандартный рекурсивный алгоритм для DFS:

базовый случай: если текущий узел равен Null, вернуть false
рекурсивный шаг: в противном случае проверяется значение текущего узла, возвращается true, если совпадает, в противном случае выполняется рекурсия по дочерним узлам

При коротком замыкании это выглядит так:

проверить значение текущего узла, вернуть true, если совпадает,
в противном случае, для потомков, если не Null, то рекурсия.

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

В случае идеального бинарного дерева высоты h имеется 2 ^{h +1} −1 узлов и 2 ^{h +1} нулевых указателей в качестве дочерних элементов (по 2 для каждого из 2 ^h листьев), поэтому в худшем случае короткое замыкание сокращает количество вызовов функций вдвое.

В языке C стандартный рекурсивный алгоритм может быть реализован следующим образом:

bool tree_contains ( struct node * tree_node , int i ) { if ( tree_node == NULL ) return false ; // базовый случай else if ( tree_node -> data == i ) return true ; else return tree_contains ( tree_node -> left , i ) || tree_contains ( tree_node -> right , i ); }

Укороченный алгоритм может быть реализован следующим образом:

// Функция-обертка для обработки пустого дерева bool tree_contains ( struct node * tree_node , int i ) { if ( tree_node == NULL ) return false ; // пустое дерево else return tree_contains_do ( tree_node , i ); // вызов вспомогательной функции }                  // Предполагается, что tree_node != NULL bool tree_contains_do ( struct node * tree_node , int i ) { if ( tree_node -> data == i ) return true ; // найдено else // рекурсия return ( tree_node -> left && tree_contains_do ( tree_node -> left , i )) || ( tree_node -> right && tree_contains_do ( tree_node -> right , i )); }

Обратите внимание на использование сокращенной оценки булевых операторов && (AND), так что рекурсивный вызов выполняется только в том случае, если узел является допустимым (ненулевым). Обратите внимание, что хотя первый член в AND является указателем на узел, второй член является булевой величиной, поэтому общее выражение вычисляется как булево. Это распространенная идиома в рекурсивном сокращенном замыкании. Это в дополнение к сокращенной оценке булевого оператора || (OR), чтобы проверять только правого потомка, если левый потомок терпит неудачу. Фактически, весь поток управления этих функций можно заменить одним булевским выражением в операторе return, но при этом страдает разборчивость без какой-либо выгоды для эффективности.

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

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

Рекурсия против итерации

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

Сравните шаблоны для вычисления x _{n ,} определенные как x _n = f(n, x _n-1 ) из x _base :

Для императивного языка накладные расходы заключаются в определении функции, а для функционального языка накладные расходы заключаются в определении переменной-аккумулятора x.

Например, факториальную функцию можно реализовать итеративно в языке C, присваивая ее переменной индекса цикла и переменной-аккумулятору, а не передавая аргументы и возвращая значения с помощью рекурсии:

unsigned int factorial ( unsigned int n ) { unsigned int product = 1 ; // пустой продукт равен 1 while ( n ) { product *= n ; -- n ; } return product ; }

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

Большинство языков программирования, используемых сегодня, допускают прямую спецификацию рекурсивных функций и процедур. Когда вызывается такая функция, среда выполнения программы отслеживает различные экземпляры функции (часто с использованием стека вызовов , хотя могут использоваться и другие методы). Каждая рекурсивная функция может быть преобразована в итеративную функцию путем замены рекурсивных вызовов на итеративные управляющие конструкции и имитации стека вызовов с помощью стека , явно управляемого программой. ^[9]^[10]

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

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

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

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

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

В некоторых языках программирования максимальный размер стека вызовов намного меньше, чем доступное пространство в куче , и рекурсивные алгоритмы, как правило, требуют больше места в стеке, чем итеративные алгоритмы. Следовательно, эти языки иногда накладывают ограничение на глубину рекурсии, чтобы избежать переполнения стека ; Python является одним из таких языков. ^[13] Обратите внимание на предостережение ниже относительно особого случая хвостовой рекурсии .

Уязвимость

Поскольку рекурсивные алгоритмы могут быть подвержены переполнению стека, они могут быть уязвимы для патологического или вредоносного ввода. ^[14] Некоторые вредоносные программы специально нацелены на стек вызовов программы и используют его рекурсивную природу. ^[15] Даже при отсутствии вредоносных программ переполнение стека, вызванное неограниченной рекурсией, может быть фатальным для программы, а логика обработки исключений может не предотвратить завершение соответствующего процесса . [ ^16]

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

Многократно рекурсивные задачи по своей сути рекурсивны, поскольку им необходимо отслеживать предшествующее состояние. Одним из примеров является обход дерева, как в поиске в глубину ; хотя используются как рекурсивные, так и итеративные методы, ^[17] они контрастируют с обходом списка и линейным поиском в списке, который является однократно рекурсивным и, следовательно, естественно итеративным методом. Другие примеры включают алгоритмы «разделяй и властвуй», такие как быстрая сортировка , и функции, такие как функция Аккермана . Все эти алгоритмы могут быть реализованы итеративно с помощью явного стека , но усилия программиста, необходимые для управления стеком, и сложность полученной программы, возможно, перевешивают любые преимущества итеративного решения.

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

Рекурсивные алгоритмы можно заменить нерекурсивными аналогами. ^[18] Одним из методов замены рекурсивных алгоритмов является их имитация с использованием динамической памяти вместо стековой памяти . ^[19] Альтернативой является разработка алгоритма замены, полностью основанного на нерекурсивных методах, что может быть сложным. ^[20] Например, рекурсивные алгоритмы для сопоставления подстановочных знаков , такие как алгоритм Wildmat Рича Сальца , [ ^21] когда-то были типичными. Нерекурсивные алгоритмы для той же цели, такие как алгоритм сопоставления подстановочных знаков Краусса , были разработаны, чтобы избежать недостатков рекурсии ^[22] и улучшались только постепенно на основе таких методов, как сбор тестов и профилирование производительности. ^[23]

Хвост-рекурсивные функции

Хвостовые рекурсивные функции — это функции, в которых все рекурсивные вызовы являются хвостовыми вызовами и, следовательно, не создают никаких отложенных операций. Например, функция gcd (снова показанная ниже) является хвостовой рекурсией. Напротив, функция factorial (также показанная ниже) не является хвостовой рекурсией; поскольку ее рекурсивный вызов не находится в хвостовой позиции, она создает отложенные операции умножения, которые должны быть выполнены после завершения последнего рекурсивного вызова. С компилятором или интерпретатором , который обрабатывает хвостовые рекурсивные вызовы как переходы , а не вызовы функций, хвостовая рекурсивная функция, такая как gcd, будет выполняться с использованием константного пространства. Таким образом, программа по сути итеративна, что эквивалентно использованию императивных структур управления языком, таких как циклы «for» и «while».

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

Порядок исполнения

Рассмотрим эти две функции:

Функция 1

void recursiveFunction ( int num ) { printf ( "%d \n " , num ); если ( num < 4 ) recursiveFunction ( num + 1 ); }

Функция 2

void recursiveFunction ( int num ) { if ( num < 4 ) recursiveFunction ( num + 1 ); printf ( "%d \n " , num ); }

Выходные данные функции 2 совпадают с выходными данными функции 1, но с перестановкой строк.

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

Также обратите внимание, что порядок операторов печати обратный, что связано со способом хранения функций и операторов в стеке вызовов .

Рекурсивные процедуры

Факториал

Классическим примером рекурсивной процедуры является функция, используемая для вычисления факториала натурального числа :

\operatorname {факт} (n)={\begin{cases}1&{\mbox{if}}n=0\\n\cdot \operatorname {факт} (n-1)&{\mbox{if}}n>0\\\end{cases}}

Функцию также можно записать в виде рекуррентного соотношения :

b_{n}=nb_{n-1}

b_{0}=1

Эта оценка рекуррентного соотношения демонстрирует вычисления, которые будут выполнены при оценке приведенного выше псевдокода:

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

Приведенный выше императивный код эквивалентен этому математическому определению с использованием переменной-аккумулятора $t$ :

{\begin{aligned}\operatorname {fact} (n)&=\operatorname {fact_{acc}} (n,1)\\\operatorname {fact_{acc}} (n,t)&={\begin{cases}t&{\mbox{if }}n=0\\\operatorname {fact_{acc}} (n-1,nt)&{\mbox{if }}n>0\\\end{cases}}\end{aligned}}

Приведенное выше определение напрямую переносится на языки функционального программирования , такие как Scheme ; это пример итерации, реализованной рекурсивно.

Наибольший общий делитель

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

Определение функции :

\gcd(x,y)={\begin{cases}x&{\mbox{if }}y=0\\\gcd(y,\operatorname {remainder} (x,y))&{\mbox{if }}y>0\\\end{cases}}

Рекуррентное соотношение для наибольшего общего делителя, где выражает остаток : $x\%y$ $x/y$

\gcd(x,y)=\gcd(y,x\%y)

если

y\neq 0

\gcd(x,0)=x

Рекурсивная программа выше является хвостовой рекурсией ; она эквивалентна итеративному алгоритму, а вычисление, показанное выше, показывает шаги оценки, которые были бы выполнены языком, который устраняет хвостовые вызовы. Ниже приведена версия того же алгоритма с использованием явной итерации, подходящая для языка, который не устраняет хвостовые вызовы. Сохраняя свое состояние полностью в переменных x и y и используя циклическую конструкцию, программа избегает выполнения рекурсивных вызовов и увеличения стека вызовов.

Итеративный алгоритм требует временной переменной, и даже при наличии знаний об алгоритме Евклида сложнее понять процесс простым взглядом, хотя эти два алгоритма очень похожи по своим шагам.

Башни Ханоя

«Ханойские башни» — математическая головоломка, решение которой иллюстрирует рекурсию. ^[24]^[25] Есть три колышка, на которые можно положить стопки дисков разного диаметра. Диск большего размера никогда не может быть положен на меньший. Начиная с n дисков на одном колышке, их нужно перекладывать на другой колышек по одному за раз. Какое наименьшее количество шагов нужно сделать, чтобы переместить стопку?

Определение функции :

\operatorname {hanoi} (n)={\begin{cases}1&{\mbox{if }}n=1\\2\cdot \operatorname {hanoi} (n-1)+1&{\mbox{if }}n>1\\\end{cases}}

Рекуррентное соотношение для Ханоя :

h_{n}=2h_{n-1}+1

h_{1}=1

Примеры реализации:

Хотя не все рекурсивные функции имеют явное решение, последовательность Ханойской башни можно свести к явной формуле. ^[26]

Двоичный поиск

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

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

Пример реализации бинарного поиска на языке C:

 /*  Вызов binary_search с правильными начальными условиями. ВХОД:  data — массив целых чисел, ОТСОРТИРОВАННЫХ ПО ВОЗРАСТАНИЮ,  toFind — целое число для поиска,  count — общее количество элементов в массиве. ВЫВОД:  результат binary_search*/ int search ( int * data , int toFind , int count ) { // Начало = 0 (начальный индекс) // Конец = count - 1 (верхний индекс) return binary_search ( data , toFind , 0 , count -1 ); }                 /*  Алгоритм двоичного поиска. ВХОД:  data — массив целых чисел, ОТСОРТИРОВАННЫХ ПО ВОЗРАСТАНИЮ,  toFind — искомое целое число,  start — минимальный индекс массива,  end — максимальный индекс массива  ВЫХОД:  позиция целого числа toFind в массиве data,  -1, если не найдено */ int binary_search ( int * data , int toFind , int start , int end ) { //Получить среднюю точку. int mid = start + ( end - start ) / 2 ; //Целочисленное деление                     if ( start > end ) // Условие остановки (базовый случай) return -1 ; else if ( data [ mid ] == toFind ) // Найдено, вернуть индекс return mid ; else if ( data [ mid ] > toFind ) // Данные больше toFind, поиск в нижней половине return binary_search ( data , toFind , start , mid -1 ); else // Данные меньше toFind, поиск в верхней половине return binary_search ( data , toFind , mid + 1 , end ); }

Рекурсивные структуры данных (структурная рекурсия)

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

«Рекурсивные алгоритмы особенно подходят, когда основная проблема или данные, которые необходимо обработать, определены в рекурсивных терминах». ^[27]

Примеры в этом разделе иллюстрируют то, что известно как «структурная рекурсия». Этот термин относится к тому факту, что рекурсивные процедуры действуют на данные, которые определены рекурсивно.

Пока программист выводит шаблон из определения данных, функции используют структурную рекурсию. То есть рекурсии в теле функции потребляют некоторую непосредственную часть заданного составного значения. ^[7]

Связанные списки

Ниже приведено определение структуры узла связанного списка на языке C. Обратите особое внимание на то, как узел определяется в терминах самого себя. Элемент «next» struct node является указателем на другой struct node , фактически создавая тип списка.

struct node { int data ; // некоторые целочисленные данные struct node * next ; // указатель на другой узел структуры };

Поскольку структура данных узла структуры определена рекурсивно, процедуры, которые работают с ней, могут быть реализованы естественным образом как рекурсивные процедуры. Процедура list_print , определенная ниже, проходит по списку, пока он не станет пустым (т. е. указатель списка не будет иметь значение NULL). Для каждого узла она печатает элемент данных (целое число). В реализации на языке C список остается неизменным с помощью процедуры list_print .

void list_print ( struct node * list ) { if ( list != NULL ) // базовый случай { printf ( "%d " , list -> data ); // вывести целочисленные данные, за которыми следует пробел list_print ( list -> next ); // рекурсивный вызов на следующем узле } }

Двоичные деревья

Ниже приведено простое определение узла бинарного дерева. Как и узел для связанных списков, он определяется в терминах самого себя, рекурсивно. Существует два самореферентных указателя: левый (указывающий на левое поддерево) и правый (указывающий на правое поддерево).

struct node { int data ; // некоторые целочисленные данные struct node * left ; // указатель на левое поддерево struct node * right ; // указатель на правое поддерево };

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

// Проверка, содержит ли tree_node i; вернуть 1, если да, и 0, если нет. int tree_contains ( struct node * tree_node , int i ) { if ( tree_node == NULL ) вернуть 0 ; // базовый случай иначе if ( tree_node -> data == i ) вернуть 1 ; иначе вернуть tree_contains ( tree_node -> left , i ) || tree_contains ( tree_node -> right , i ); }

Для любого вызова tree_contains , как определено выше, будет сделано не более двух рекурсивных вызовов .

// Обход в обратном порядке: void tree_print ( struct node * tree_node ) { if ( tree_node != NULL ) { // базовый случай tree_print ( tree_node -> left ); // перейти влево printf ( "%d " , tree_node -> data ); // вывести целое число, за которым следует пробел tree_print ( tree_node -> right ); // перейти вправо } }

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

Обход файловой системы

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

импорт java.io.File ; открытый класс FileSystem {   public static void main ( String [] args ) {      траверс ();}/** * Получает корни файловой системы * Продолжает рекурсивный обход файловой системы */частный статический void traverse () {    Файл [] fs = Файл . listRoots ();   для ( int i = 0 ; i < fs . длина ; i ++ ) {         Система.out.println ( fs [ i ] ) ;если ( fs [ i ] . isDirectory () && fs [ i ] . canRead ()) {    rtraverse ( fs [ i ] );}}}/** * Рекурсивный обход заданного каталога * * @param fd указывает начальную точку обхода */частный статический void rtraverse ( Файл fd ) {     Файл [] fss = fd . listFiles ();   для ( int i = 0 ; i < fss . длина ; i ++ ) {         Система.out.println ( fss [ i ] ) ;если ( fss [ i ] . isDirectory () && fss [ i ] . canRead ()) {    rtraverse ( fss [ i ] );}}}}

Этот код представляет собой как рекурсию, так и итерацию — файлы и каталоги перебираются, и каждый каталог открывается рекурсивно.

Метод «rtraverse» является примером прямой рекурсии, тогда как метод «traverse» является функцией-оберткой.

«Базовый» сценарий заключается в том, что в данной файловой системе всегда будет фиксированное количество файлов и/или каталогов.

Эффективность рекурсивных алгоритмов по времени

Эффективность рекурсивных алгоритмов по времени можно выразить в виде рекуррентного соотношения в нотации Big O. Затем их (обычно) можно упростить до одного термина Big-O.

Правило сокращения (основная теорема)

Если временная сложность функции имеет вид $T(n)=a\cdot T(n/b)+f(n)$

Тогда большое О временной сложности выглядит следующим образом:

Если для некоторой константы , то $f(n)=O(n^{\log _{b}a-\varepsilon })$ $\varepsilon >0$ $T(n)=\Theta (n^{\log _{b}a})$
Если , то $f(n)=\Theta (n^{\log _{b}a})$ $T(n)=\Theta (n^{\log _{b}a}\log n)$
Если для некоторой константы , и если для некоторой константы $c$ $< 1$ и все достаточно большие $n$ , то $f(n)=\Omega (n^{\log _{b}a+\varepsilon })$ $\varepsilon >0$ $a\cdot f(n/b)\leq c\cdot f(n)$ $T(n)=\Theta (f(n))$

где $a$ представляет собой количество рекурсивных вызовов на каждом уровне рекурсии, $b$ представляет собой коэффициент, на который меньше входные данные для следующего уровня рекурсии (т. е. количество частей, на которые вы делите задачу), а $f (n)$ представляет собой работу, которую функция выполняет независимо от какой-либо рекурсии (например, разбиения, рекомбинации) на каждом уровне рекурсии.

Рекурсия в логическом программировании

В процедурной интерпретации логических программ предложения (или правила) формы рассматриваются как процедуры, которые сводят цели формы к подцелям формы . Например, предложения Пролога :A :- BAB

путь ( X , Y )  :-  дуга ( X , Y ). путь ( X , Y )  :-  дуга ( X , Z ),  путь ( Z , Y ).

определить процедуру, которая может быть использована для поиска пути из X в Y , либо путем нахождения прямой дуги из X в Y , либо путем нахождения дуги из X в Z , а затем рекурсивного поиска пути из Z в Y . Пролог выполняет процедуру, рассуждая сверху вниз (или назад ) и просматривая пространство возможных путей в глубину, по одной ветви за раз. Если он пытается выполнить второе предложение и конечно не может найти путь из Z в Y , он возвращается и пытается найти дугу из X в другой узел, а затем ищет путь из этого другого узла в Y .

Однако в логическом чтении логических программ предложения понимаются декларативно как универсально квантифицированные условные предложения. Например, рекурсивное предложение процедуры поиска пути понимается как представление знания о том, что для каждого X , Y и Z , если есть дуга из X в Z и путь из Z в Y , то есть путь из X в Y. В символической форме:

\forall X,Y,Z(arc(X,Z)\land path(Z,Y)\rightarrow path(X,Y)).

Логическое чтение освобождает читателя от необходимости знать, как предложение используется для решения проблем. Предложение может использоваться сверху вниз, как в Prolog, для сведения проблем к подзадачам. Или его можно использовать снизу вверх (или вперед ), как в Datalog , для вывода заключений из условий. Такое разделение интересов является формой абстракции , которая отделяет декларативные знания от методов решения проблем (см. Algorithm#Algorithm = Logic + Control ). ^[28]

Смотрите также

Примечания

^ Грэм, Рональд; Кнут, Дональд; Паташник, Орен (1990). "1: Рекуррентные проблемы". Конкретная математика . Эддисон-Уэсли. ISBN 0-201-55802-5.
^ Кухейл, МА; Негрейрос, Дж.; Сеффах, А. (2021). «Обучение рекурсивному мышлению с использованием отключенных видов деятельности» (PDF) . World Transactions on Engineering and Technology Education . 19 : 169–175.
^ Эпп, Сусанна (1995). Дискретная математика с приложениями (2-е изд.). PWS Publishing Company. стр. 427. ISBN 978-0-53494446-9.
^ Вирт, Никлаус (1976). Алгоритмы + Структуры данных = Программы. Prentice-Hall . стр. 126. ISBN 978-0-13022418-7.
^ «Функциональное программирование | Clojure для смелых и честных». www.braveclojure.com . Получено 21 октября 2020 г.
^ Феллизен и др. 2001, арт V "Генеративная рекурсия"
^ ab Felleisen, Matthias (2002). "Разработка интерактивных веб-программ". В Jeuring, Johan (ред.). Advanced Functional Programming: 4th International School (PDF) . Springer. стр. 108. ISBN 9783540448334.
^ Монган, Джон; Жигер, Эрик; Киндлер, Ноа (2013). Программирование интервью раскрыто: секреты получения следующей работы (3-е изд.). Wiley . стр. 115. ISBN 978-1-118-26136-1.
^ Хетланд, Магнус Ли (2010), Алгоритмы Python: Освоение базовых алгоритмов на языке Python, Apress, стр. 79, ISBN 9781430232384.
^ Дроздек, Адам (2012), Структуры данных и алгоритмы в C++ (4-е изд.), Cengage Learning, p. 197, ISBN 9781285415017.
^ Шиверс, Олин. «Анатомия петли — история масштаба и контроля» (PDF) . Технологический институт Джорджии . Получено 03.09.2012 .
^ Lambda the Ultimate. "Анатомия петли". Lambda the Ultimate . Получено 03.09.2012 .
^ "27.1. sys — Системно-специфичные параметры и функции — Документация Python v2.7.3". Docs.python.org . Получено 2012-09-03 .
^ Краусс, Кирк Дж. (2014). «Соответствие джокеров: эмпирический способ приручить алгоритм». Журнал доктора Добба .
^ Мюллер, Оливер (2012). «Анатомия атаки на стек и как GCC предотвращает ее». Журнал доктора Добба .
^ "Класс StackOverflowException". Библиотека классов .NET Framework . Сеть разработчиков Microsoft . 2018.
^ «Поиск в глубину (DFS): итеративная и рекурсивная реализация». Techie Delight. 2018.
^ Митрович, Иван. «Замена рекурсии итерацией». ThoughtWorks .
^ Ла, Вунг Гю (2015). «Как заменить рекурсивные функции с помощью стека и цикла while, чтобы избежать переполнения стека». CodeProject.
^ Муртель, Том (2013). «Трюки ремесла: Рекурсия к итерации, часть 2: Устранение рекурсии с помощью секретного трюка с путешествием во времени».
^ Зальц, Рич (1991). "wildmat.c". Гитхаб .
^ Краусс, Кирк Дж. (2008). «Сопоставление подстановочных знаков: алгоритм». Журнал доктора Добба .
^ Краусс, Кирк Дж. (2018). «Соответствие подстановочных знаков: улучшенный алгоритм для больших данных». Разработка для производительности.
^ Грэм, Кнут и Паташник 1990, §1.1: Ханойская башня
↑ Эпп 1995, стр. 427–430: Ханойская башня
↑ Эпп 1995, стр. 447–448: Явная формула для последовательности Ханойской башни
^ Вирт 1976, стр. 127
^ Рассел, Стюарт Дж .; Норвиг, Питер. (2021). Искусственный интеллект: современный подход §9.3, §9.4 (4-е изд.). Хобокен: Pearson. ISBN 978-0134610993. LCCN 20190474.

Ссылки

Barron, David William (1968) [1967]. Написано в Кембридже, Великобритания. Gill, Stanley (ред.). Рекурсивные методы в программировании . Macdonald Computer Monographs (1-е изд.). Лондон, Великобритания: Macdonald & Co. (Publishers) Ltd. SBN 356-02201-3.(viii+64 страницы)
Феллейзен, Маттиас; Финдлер, Роберт Б.; Флэтт, Мэтью; Кришнамурти, Шрирам (2001). Как разрабатывать программы: Введение в вычисления и программирование. MIT Press . ISBN 0262062186.
Рубио-Санчес, Мануэль (2017). Введение в рекурсивное программирование. CRC Press . ISBN 978-1-351-64717-5.
Певац, Ирена (2016). Практика рекурсии в Java . CreateSpace Независимый. ISBN 978-1-5327-1227-2.
Робертс, Эрик (2005). Рекурсивное мышление с помощью Java. Wiley . ISBN 978-0-47170146-0.
Рол, Джеффри С. (1984). Рекурсия через Паскаль. Cambridge University Press . ISBN 978-0-521-26934-6.
Хельман, Пол; Верофф, Роберт. Стены и зеркала .
Абельсон, Гарольд ; Сассман, Джеральд Джей ; Сассман, Джули (1996). Структура и интерпретация компьютерных программ (2-е изд.). MIT Press . ISBN 0-262-51087-1.
Дейкстра, Эдсгер В. (1960). «Рекурсивное программирование». Числовая математика . 2 (1): 312–318. дои : 10.1007/BF01386232. S2CID 127891023.