Рекурсия возникает, когда определение концепции или процесса зависит от более простой или предыдущей версии самого себя. [1] Рекурсия используется в различных дисциплинах, от лингвистики до логики . Наиболее распространенное применение рекурсии — в математике и информатике , где определяемая функция применяется в рамках ее собственного определения. Хотя это, очевидно, определяет бесконечное количество экземпляров (значений функции), часто это делается таким образом, что не может возникнуть бесконечный цикл или бесконечная цепочка ссылок.
Процесс, демонстрирующий рекурсию, является рекурсивным .
В математике и информатике класс объектов или методов демонстрирует рекурсивное поведение, если его можно определить двумя свойствами:
Например, ниже приведено рекурсивное определение предка человека . Предком человека является либо:
Последовательность Фибоначчи — еще один классический пример рекурсии:
Многие математические аксиомы основаны на рекурсивных правилах. Например, формальное определение натуральных чисел аксиомами Пеано можно описать так: «Ноль — натуральное число, и каждое натуральное число имеет последователя, который также является натуральным числом». [2] С помощью этого базового случая и рекурсивного правила можно сгенерировать набор всех натуральных чисел.
Другие рекурсивно определенные математические объекты включают факториалы , функции (например, рекуррентные отношения ), множества (например, троичное множество Кантора ) и фракталы .
Существуют различные более ироничные определения рекурсии; см. рекурсивный юмор.
Рекурсия — это процесс, который проходит процедура, когда один из шагов процедуры включает вызов самой процедуры. Процедура, которая проходит рекурсию, называется «рекурсивной». [3]
Чтобы понять рекурсию, необходимо признать различие между процедурой и ее выполнением. Процедура — это набор шагов, основанный на наборе правил, а выполнение процедуры предполагает фактическое следование правилам и выполнение шагов.
Рекурсия связана со ссылкой в спецификации процедуры на выполнение какой-либо другой процедуры, но не совпадает с ней.
Когда процедура определена таким образом, это немедленно создает возможность бесконечного цикла; рекурсию можно правильно использовать в определении только в том случае, если рассматриваемый шаг в определенных случаях пропускается, чтобы процедура могла завершиться.
Даже если она правильно определена, рекурсивную процедуру нелегко выполнить людям, поскольку она требует отличать новый от старого, частично выполненного вызова процедуры; это требует некоторого администрирования в отношении того, насколько далеко продвинулись различные одновременные случаи процедур. По этой причине рекурсивные определения очень редки в повседневных ситуациях.
Лингвист Ноам Хомский , среди многих других, утверждал, что отсутствие верхней границы количества грамматических предложений в языке и отсутствие верхней границы грамматической длины предложения (помимо практических ограничений, таких как время, доступное для произнесения одного ), можно объяснить как следствие рекурсии в естественном языке. [4] [5]
Это можно понять с точки зрения рекурсивного определения синтаксической категории, такой как предложение. Предложение может иметь структуру, в которой за глаголом следует другое предложение: Дороти думает, что ведьмы опасны , в котором предложение «ведьмы опасны» встречается в более широком предложении. Таким образом, предложение можно рекурсивно (очень грубо) определить как нечто, структура которого включает в себя именное словосочетание, глагол и, возможно, другое предложение. На самом деле это всего лишь частный случай математического определения рекурсии.
Это дает возможность понять креативность языка – неограниченное количество грамматических предложений – поскольку сразу предсказывает, что предложения могут иметь произвольную длину: Дороти думает, что Тото подозревает, что Железный Дровосек сказал это... . Помимо предложений, которые можно определить рекурсивно, существует множество структур, и, следовательно, множество способов, с помощью которых предложение может встраивать экземпляры одной категории в другую. [6] За прошедшие годы языки в целом оказались пригодными для такого рода анализа.
Общепринятая идея о том, что рекурсия является важнейшим свойством человеческого языка, была оспорена Дэниелом Эвереттом на основании его утверждений о языке пираха . Эндрю Невинс, Дэвид Песецкий и Силин Родригес — среди многих, кто выступал против этого. [7] В любом случае можно утверждать, что литературная самоотсылка отличается от математической или логической рекурсии. [8]
Рекурсия играет решающую роль не только в синтаксисе, но и в семантике естественного языка . Слово и , например, можно истолковать как функцию, которая может применяться к значениям предложений для создания новых предложений, а также к значениям именных фраз, значений глагольных фраз и других. Это также может применяться к непереходным глаголам, переходным глаголам или дипереходным глаголам. Чтобы обеспечить для него единое обозначение, которое было бы достаточно гибким и обычно определялось так, чтобы оно могло принимать любое из этих различных типов значений в качестве аргументов. Это можно сделать, определив его для простого случая, в котором он объединяет предложения, а затем рекурсивно определив другие случаи в терминах простого. [9]
Рекурсивная грамматика — это формальная грамматика , содержащая рекурсивные правила производства . [10]
Рекурсия иногда используется с юмором в учебниках по информатике, программированию, философии или математике, обычно давая круговое определение или ссылку на самого себя , в которой предполагаемый рекурсивный шаг не приближается к базовому случаю, а вместо этого приводит к бесконечному регрессу. . В таких книгах нет ничего необычного в том, что они включают в глоссарий анекдоты вроде:
Вариант можно найти на странице 269 указателя некоторых изданий книги Брайана Кернигана и Денниса Ритчи «Язык программирования C» ; запись индекса рекурсивно ссылается на себя («рекурсия 86, 139, 141, 182, 202, 269»). Ранние версии этой шутки можно найти в книге « Давайте поговорим о Лиспе» Лорана Сиклосси (опубликованной издательством Prentice Hall PTR 1 декабря 1975 года, дата авторских прав — 1976 год) и в книге «Программные инструменты» Кернигана и Плаугера (опубликованной Addison-Wesley Professional на английском языке). 11 января 1976 г.). Шутка также появляется в книге «Среда программирования UNIX» Кернигана и Пайка. Его не было в первом издании The C Programming Language . Эта шутка является частью фольклора функционального программирования и была широко распространена в сообществе функционального программирования еще до публикации вышеупомянутых книг. [12] [13]
Другая шутка гласит: «Чтобы понять рекурсию, вы должны понять рекурсию». [11] В англоязычной версии поисковой системы Google при поиске по запросу «рекурсия» сайт предлагает «Вы имели в виду: рекурсия ». [14] Альтернативная форма от Эндрю Плоткина следующая : «Если вы уже знаете, что такое рекурсия, просто запомните ответ. В противном случае найдите кого-нибудь, кто стоит к Дугласу Хофштадтеру ближе , чем вы; затем спросите его или ее, что такое рекурсия». является."
Рекурсивные аббревиатуры — еще один пример рекурсивного юмора. PHP , например, означает «Препроцессор гипертекста PHP», WINE означает «WINE не является эмулятором», GNU означает «GNU's not Unix», а SPARQL означает «Протокол SPARQL и язык запросов RDF».
Канонический пример рекурсивно определенного множества — натуральные числа :
В математической логике аксиомы Пеано (или постулаты Пеано или аксиомы Дедекинда-Пеано) представляют собой аксиомы натуральных чисел, представленные в 19 веке немецким математиком Рихардом Дедекиндом и итальянским математиком Джузеппе Пеано . Аксиомы Пеано определяют натуральные числа, относящиеся к рекурсивной функции-преемнику, а сложение и умножение - как рекурсивные функции.
Другим интересным примером является набор всех «доказуемых» утверждений в аксиоматической системе , определенных в терминах процедуры доказательства , которая индуктивно (или рекурсивно) определяется следующим образом:
Правила конечного подразделения — это геометрическая форма рекурсии, которую можно использовать для создания фрактальных изображений. Правило подразделения начинается с набора многоугольников, помеченных конечным числом меток, а затем каждый многоугольник подразделяется на меньшие помеченные многоугольники способом, который зависит только от меток исходного многоугольника. Этот процесс можно повторять. Стандартный метод «средних третей» для создания множества Кантора — это правило подразделения, как и барицентрическое подразделение .
Функция может быть рекурсивно определена относительно самой себя. Знакомый пример — числовая последовательность Фибоначчи: F ( n ) = F ( n — 1) + F ( n — 2). Чтобы такое определение было полезным, оно должно быть сведено к нерекурсивно определенным значениям: в этом случае F (0) = 0 и F (1) = 1.
Применение стандартной техники доказательства по случаям к рекурсивно определенным наборам или функциям, как описано в предыдущих разделах, дает структурную индукцию — мощное обобщение математической индукции, широко используемое для вывода доказательств в математической логике и информатике.
Динамическое программирование — это подход к оптимизации , который переформулирует задачу многопериодной или многошаговой оптимизации в рекурсивной форме. Ключевым результатом динамического программирования является уравнение Беллмана , которое записывает значение задачи оптимизации на более раннем этапе (или более раннем этапе) через ее значение в более поздний момент времени (или более поздний шаг).
В теории множеств это теорема, гарантирующая существование рекурсивно определенных функций. Для заданного набора X , элемента a из X и функции f : X → X теорема утверждает, что существует единственная функция (где обозначает набор натуральных чисел, включая ноль), такая что
для любого натурального числа n .
Дедекинд был первым, кто поставил проблему однозначного определения теоретико-множественных функций с помощью рекурсии и дал набросок аргумента в эссе 1888 года «Was sind und was sollen die Zahlen?» [15]
Возьмем две функции и такие, что:
где a — элемент X.
Методом математической индукции можно доказать , что F ( n ) = G ( n ) для всех натуральных чисел n :
По индукции F ( n ) = G ( n ) для всех .
Распространенный метод упрощения — разделить проблему на подзадачи одного типа. В технике компьютерного программирования это называется « разделяй и властвуй» , и он является ключом к разработке многих важных алгоритмов. «Разделяй и властвуй» представляет собой нисходящий подход к решению проблем, при котором проблемы решаются путем решения все меньших и меньших экземпляров. Противоположный подход – динамическое программирование . Этот подход представляет собой подход «снизу вверх», при котором проблемы решаются путем решения все более и более крупных экземпляров, пока не будет достигнут желаемый размер.
Классическим примером рекурсии является определение функции факториал , приведенное здесь в коде Python :
def факториал ( n ): если n > 0 : вернуть n * факториал ( n - 1 ) иначе : вернуть 1
Функция рекурсивно вызывает себя на меньшей версии входных данных (n - 1)
и умножает результат рекурсивного вызова на n
, пока не достигнет базового случая , аналогично математическому определению факториала.
Рекурсия в компьютерном программировании иллюстрируется, когда функция определяется в терминах более простых, часто меньших версий самой себя. Затем решение проблемы разрабатывается путем объединения решений, полученных из более простых версий проблемы. Одним из примеров применения рекурсии являются анализаторы языков программирования. Большим преимуществом рекурсии является то, что бесконечный набор возможных предложений, конструкций или других данных может быть определен, проанализирован или создан с помощью ограниченной компьютерной программы.
Рекуррентные отношения — это уравнения, которые рекурсивно определяют одну или несколько последовательностей. Некоторые конкретные виды рекуррентных отношений можно «решить» для получения нерекурсивного определения (например, выражения в замкнутой форме ).
Использование рекурсии в алгоритме имеет как преимущества, так и недостатки. Главным преимуществом обычно является простота инструкции. Основным недостатком является то, что использование памяти рекурсивными алгоритмами может расти очень быстро, что делает их непрактичными для более крупных экземпляров.
Формы, которые кажутся созданными в результате рекурсивных процессов, иногда появляются у растений и животных, например, в ветвящихся структурах, в которых одна большая часть разветвляется на две или более похожие более мелкие части. Одним из примеров является брокколи романеско . [16]
Авторы используют концепцию рекурсивности , чтобы выдвинуть на первый план ситуацию, в которой оказываются именно ученые- социологи , производящие знания о мире, частью которого они всегда уже являются. [17] [18] По словам Одри Алехандро, «как социологи, рекурсивность нашего состояния связана с тем фактом, что мы являемся одновременно субъектами (поскольку дискурсы являются средой, с помощью которой мы анализируем) и объектами академических дискурсов, которые мы производим ( поскольку мы — социальные агенты, принадлежащие миру, который мы анализируем). [19] Исходя из этого, она определяет в рекурсивности фундаментальную проблему в производстве эмансипаторного знания, которая требует применения рефлексивных усилий:
мы социализируемся в дискурсы и диспозиции, порождаемые социально-политическим порядком, которому мы стремимся бросить вызов, социально-политическим порядком, который мы, следовательно, можем бессознательно воспроизводить, стремясь сделать обратное. Рекурсивность нашей ситуации как ученых – и, точнее, тот факт, что диспозиционные инструменты, которые мы используем для производства знаний о мире, сами производятся этим миром – одновременно доказывает жизненную необходимость реализации рефлексивности на практике и представляет собой главную проблему в делать это.
- Одри Алехандро, Алехандро (2021)
В науке управления рекурсию иногда называют процессом итерации уровней абстракции в крупных бизнес-структурах. [20] Типичным примером является рекурсивная природа управленческих иерархий , начиная от линейного руководства и заканчивая высшим руководством и менеджерами среднего звена . Он также охватывает более широкий вопрос структуры капитала в корпоративном управлении . [21]
Матрешка является физическим художественным примером рекурсивной концепции. [22]
Рекурсия использовалась в картинах со времен « Триптиха Стефанески» Джотто , созданного в 1320 году. На его центральной панели изображена коленопреклоненная фигура кардинала Стефанески, держащего сам триптих как подношение. [23] [24] Эта практика более широко известна как эффект Дросте , пример техники Mise en abyme .
« Галерея печати» М. К. Эшера (1956) — это гравюра, на которой изображен искаженный город, содержащий галерею, рекурсивно содержащую изображение, и так до бесконечности . [25]
В фильме «Начало» в разговорной речи используется добавление суффикса -ception к существительному, чтобы в шутку указать на рекурсию чего-либо. [26]
Еще примеры рекурсии: Русские матрешки. Каждая кукла изготовлена из цельного дерева или полая и содержит внутри еще одну матрешку.