Рекурсия

Чтобы узнать о других значениях, см. Рекурсия (значения) .

Визуальная форма рекурсии, известная как эффект Дросте . Женщина на этом изображении держит объект, который содержит меньшее изображение ее руки с идентичным объектом, которое, в свою очередь, содержит меньшее изображение ее самой, держащей идентичный объект, и так далее. Droste 1904 г. Банка какао , дизайн Яна Миссе.

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

Процесс, демонстрирующий рекурсию, является рекурсивным .

Формальные определения

Уроборос — древний символ, изображающий змею или дракона, пожирающего собственный хвост.

В математике и информатике класс объектов или методов демонстрирует рекурсивное поведение, если его можно определить двумя свойствами:

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

человека Например, ниже приведено рекурсивное определение предка . Предком человека является либо:

• Родитель ( базовый случай ) или
• Предок родителя ( рекурсивный шаг ).

Последовательность Фибоначчи — еще один классический пример рекурсии:

Fib(0) = 0 в качестве базового случая 1,

Fib(1) = 1 как базовый вариант 2,

Для всех целых чисел n > 1 Fib ( n ) = Fib( n − 1) + Fib( n − 2) .

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

Другие рекурсивно определенные математические объекты включают факториалы , функции (например, рекуррентные отношения ), множества (например, троичное множество Кантора ) и фракталы .

Существуют различные более ироничные определения рекурсии; см . рекурсивный юмор .

Неформальное определение

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

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

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

Рекурсия связана со ссылкой в ​​спецификации процедуры на выполнение какой-либо другой процедуры, но не совпадает с ней.

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

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

На языке

Лингвист Ноам Хомский , среди многих других, утверждал, что отсутствие верхней границы количества грамматических предложений в языке и отсутствие верхней границы грамматической длины предложения (помимо практических ограничений, таких как время, доступное для произнесения одного ), можно объяснить как следствие рекурсии в естественном языке.

Это можно понять с точки зрения рекурсивного определения синтаксической категории, такой как предложение. Предложение может иметь структуру, в которой за глаголом следует другое предложение: Дороти думает, что ведьмы опасны , в котором предложение «ведьмы опасны» встречается в более широком предложении. Таким образом, предложение можно рекурсивно (очень грубо) определить как нечто, структура которого включает в себя именное словосочетание, глагол и, возможно, другое предложение. На самом деле это всего лишь частный случай математического определения рекурсии.

Это дает возможность понять креативность языка – неограниченное количество грамматических предложений – поскольку сразу предсказывает, что предложения могут иметь произвольную длину: Дороти думает, что Тото подозревает, что Железный Дровосек сказал это... . Помимо предложений, существует множество структур, которые можно определить рекурсивно, и, следовательно, множество способов, с помощью которых предложение может встраивать экземпляры одной категории в другую. С течением времени языки в целом оказались пригодными для такого рода анализа.

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

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

Рекурсивная грамматика — это формальная грамматика , содержащая рекурсивные правила производства .

Рекурсивный юмор

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

Рекурсия, см. Рекурсия .

Вариант можно найти на странице 269 указателя некоторых изданий Брайана Кернигана и Денниса Ритчи книги «Язык программирования C» ; запись индекса рекурсивно ссылается на себя («рекурсия 86, 139, 141, 182, 202, 269»). Ранние версии этой шутки можно найти в книге « Давайте поговорим о Лиспе» Лорана Сиклосси (опубликованной издательством Prentice Hall PTR 1 декабря 1975 года, дата авторских прав — 1976 год) и в книге «Программные инструменты» Кернигана и Плаугера (опубликованной Addison-Wesley Professional на английском языке). 11 января 1976 г.). Шутка также появляется в книге «Среда программирования UNIX» Кернигана и Пайка. Его не было в первом издании The C Programming Language . Эта шутка является частью фольклора функционального программирования и была широко распространена в сообществе функционального программирования еще до публикации вышеупомянутых книг.

Мемориальная доска посвящена проекту рекурсивной истории Торонто.

Другая шутка гласит: «Чтобы понять рекурсию, вы должны понять рекурсию». В англоязычной версии поисковой системы Google при поиске по запросу «рекурсия» сайт предлагает «Вы имели в виду: рекурсия ». следующая Альтернативная форма от Эндрю Плоткина : «Если вы уже знаете, что такое рекурсия, просто запомните ответ. В противном случае найдите кого-нибудь, кто стоит к Дугласу Хофштадтеру ближе , чем вы; затем спросите его или ее, что такое рекурсия».

Рекурсивные аббревиатуры — еще один пример рекурсивного юмора. PHP , например, означает «Препроцессор гипертекста PHP», WINE означает «WINE не является эмулятором», GNU означает «GNU's not Unix», а SPARQL означает «Протокол SPARQL и язык запросов RDF».

По математике

Треугольник Серпинского — ограниченная рекурсия треугольников, образующих фрактал.

Рекурсивно определенные множества

Основная статья: Рекурсивное определение

Пример: натуральные числа

См. Также: Замыкание (математика)

Канонический пример рекурсивно определенного множества — натуральные числа :

0 находится в $\mathbb {N}$

если n находится в $\mathbb {N}$, то n + 1 находится в $\mathbb {N}$

Набор натуральных чисел — это наименьший набор, удовлетворяющий двум предыдущим свойствам.

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

Пример: Процедура доказательства

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

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

Правила конечного подразделения

Основная статья: Правило конечного подразделения

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

Функциональная рекурсия

Функция может быть рекурсивно определена относительно самой себя. Знакомый пример — числовая последовательность Фибоначчи : F ( n ) = F ( n − 1) + F ( n − 2). Чтобы такое определение было полезным, оно должно быть сведено к нерекурсивно определенным значениям: в этом случае F (0) = 0 и F (1) = 1.

Доказательства, включающие рекурсивные определения.

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

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

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

Теорема о рекурсии

В теории множеств это теорема, гарантирующая существование рекурсивно определенных функций. Учитывая множество X , элемент a из X и функцию f : X → X , теорема утверждает, что существует единственная функция $F:\mathbb {N} \to X$ (где $\mathbb {N}$ обозначает набор натуральных чисел, включая ноль), таких, что

$F(0)=a$

$F(n+1)=f(F(n))$

для любого натурального числа n .

Дедекинд был первым, кто поставил проблему однозначного определения теоретико-множественных функций на $\mathbb {N}$ путем рекурсии и дал набросок аргумента в эссе 1888 года «Что такое числа и что они должны делать?»

Доказательство уникальности

Возьмите две функции $F:\mathbb {N} \to X$ и $G:\mathbb {N} \to X$ такой, что:

$F(0)=a$

$G(0)=a$

$F(n+1)=f(F(n))$

$G(n+1)=f(G(n))$

где a элемент X. —

можно доказать Методом математической индукции , что F ( n ) = G ( n ) для всех натуральных чисел. н :

Базовый случай : F (0) = a = G (0), поэтому равенство справедливо для n = 0 .

Индуктивный шаг : предположим, что F ( k ) = G ( k ) для некоторого $k\in \mathbb {N}$. Тогда F ( k + 1) = f ( F ( k )) = f ( G ( k )) = G ( k + 1) .

Следовательно, из F ( k ) = G ( k ) следует F ( k + 1) = G ( k + 1) .

По индукции F ( n ) = G ( n ) для всех $n\in \mathbb {N}$.

В информатике

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

Распространенный метод упрощения — разделить проблему на подзадачи одного типа. В технике компьютерного программирования это называется «разделяй и властвуй» , и он является ключом к разработке многих важных алгоритмов. «Разделяй и властвуй» представляет собой нисходящий подход к решению проблем, при котором проблемы решаются путем решения все меньших и меньших экземпляров. Противоположный подход – динамическое программирование . Этот подход представляет собой подход «снизу вверх», при котором проблемы решаются путем решения все более и более крупных экземпляров, пока не будет достигнут желаемый размер.

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

def factorial(n):
    if n > 0:
        return n * factorial(n - 1)
    else:
        return 1

Функция рекурсивно вызывает себя на меньшей версии ввода. (n - 1) и умножает результат рекурсивного вызова на n, до достижения базового случая , аналогично математическому определению факториала.

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

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

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

В биологии

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

В социальных науках

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

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

- Одри Алехандро, Алехандро (2021)

В бизнесе

Дополнительная информация: Кибернетика управления.

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

В искусстве

Recursive dolls: the original set of Matryoshka dolls by Zvyozdochkin and Malyutin , 1892

Лицевая сторона , Джотто «Триптиха Стефанески» 1320 год, рекурсивно содержит изображение самого себя (поддерживаемое коленопреклоненной фигурой на центральной панели).

См. Также: Математика и искусство и зеркало бесконечности.

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

Рекурсия использовалась в картинах со времен , Джотто «Триптиха Стефанески» созданного в 1320 году. На его центральной панели изображена коленопреклоненная фигура кардинала Стефанески, держащего сам триптих как подношение. Эта практика более известна как эффект Дросте , пример техники Mise en abyme .

» М. К. Эшера ( «Галерея печати 1956) — это гравюра, на которой изображен искаженный город, содержащий галерею, рекурсивно содержащую изображение, и так до бесконечности .

В культуре

В фильме «Начало» в разговорной речи используется добавление суффикса -ception к существительному, чтобы в шутку указать на рекурсию чего-либо.

См. также

• Corecursion - тип алгоритма в информатике.
• Рекурсия курса значений - метод определения теоретико-числовых функций с помощью рекурсии.
• Цифровая бесконечность - термин в теоретической лингвистике
• Мечта во сне (стихотворение) - Стихотворение Эдгара Аллана По. Страницы с краткими описаниями целей перенаправления.
• Эффект Дросте – рекурсивный визуальный эффект
• Ложное пробуждение – Яркий и убедительный сон о пробуждении ото сна.
• Комбинатор с фиксированной точкой – функция Y высшего порядка, для которой Y f = f (Y f). Страницы, отображающие краткие описания целей перенаправления.
• Бесконечные композиции аналитических функций - Математическая теория бесконечно повторяющейся композиции функций
• Бесконечный цикл – идиома программирования
• Бесконечный регресс - Философская проблема
• Инфинитизм - Философская точка зрения, согласно которой знание может быть оправдано бесконечной цепочкой причин.
• Зеркало бесконечности — параллельные или наклонные зеркала, создающие меньшие отражения, которые кажутся уходящими в бесконечность.
• Итерированная функция — результат многократного применения математической функции.
• Математическая индукция - форма математического доказательства.
• Mise en abyme - Техника размещения копии изображения внутри себя или истории внутри истории.
• Reentrant (подпрограмма) - концепция компьютерного программирования. Страницы, отображающие краткие описания целей перенаправления.
• Самореференция - предложение, идея или формула, которая ссылается на себя.
• Spiegel im Spiegel - музыкальная композиция Арво Пярта 1978 года.
• Странная петля - циклическая структура, проходящая через несколько уровней иерархической системы.
• Хвостовая рекурсия – вызов подпрограммы выполняется как последнее действие процедуры. Страницы с краткими описаниями целей перенаправления.
• Самореферентная формула Таппера - формула, которая визуально представляет себя в виде графика.
• Черепахи до самого низа – утверждение о бесконечном регрессе

Библиография

• Дейкстра, Эдсгер В. (1960). «Рекурсивное программирование». Численная математика . 2 (1): 312–318. дои : 10.1007/BF01386232 . S2CID   127891023 .
• Джонсонбо, Ричард (2004). Дискретная математика . Прентис Холл. ISBN  978-0-13-117686-7 .
• Хофштадтер, Дуглас (1999). Гёдель, Эшер, Бах: вечная золотая коса . Основные книги. ISBN  978-0-465-02656-2 .
• Шенфилд, Джозеф Р. (2000). Теория рекурсии . АК Питерс Лтд. ISBN  978-1-56881-149-9 .
• Кози, Роберт Л. (2001). Логика, множества и рекурсия . Джонс и Бартлетт. ISBN  978-0-7637-1695-0 .
• Кори, Рене; Ласкар, Дэниел; Пеллетье, Дональд Х. (2001). Теория рекурсии, Теоремы Гёделя, Теория множеств, Теория моделей . Издательство Оксфордского университета. ISBN  978-0-19-850050-6 .
• Барвайз, Джон ; Мосс, Лоуренс С. (1996). Порочные круги . Центр Стэнфордского университета по изучению языка и информации. ISBN  978-0-19-850050-6 . - предлагает лечение корекурсии .
• Розен, Кеннет Х. (2002). Дискретная математика и ее приложения . Колледж МакГроу-Хилл. ISBN  978-0-07-293033-7 .
• Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Стоун, Клиффорд (2001). Введение в алгоритмы . С ISBN  978-0-262-03293-3 .
• Керниган, Б.; Ричи, Д. (1988). Язык программирования Си . Прентис Холл. ISBN  978-0-13-110362-7 .
• Стоки, Нэнси; Роберт Лукас; Эдвард Прескотт (1989). Рекурсивные методы в экономической динамике . Издательство Гарвардского университета. ISBN  978-0-674-75096-8 .
• Хангерфорд (1980). Алгебра . Спрингер. ISBN  978-0-387-90518-1 . , первая глава по теории множеств.

Внешние ссылки

• Рекурсия — учебник Алана Голда
• Заархивируйте файлы до конца
• Невинс, Эндрю и Дэвид Песецки и Силин Родригес. Доказательства и аргументация: ответ Эверетту (2009). Язык 85.3: 671--681 (2009)