Рекурсия

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

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

• 1 Формальные определения
• 2 Неформальные определения
• 3 На языке
  • 3.1 Рекурсивный юмор
• 4 В математике
  • 4.1 Рекурсивно определенные множества
    • 4.1.1 Пример: натуральные числа
    • 4.1.2 Пример: процедура доказательства
  • 4.2 Правила конечного подразделения
  • 4.3 Функциональная рекурсия
  • 4.4 Доказательства с использованием рекурсивных определений
  • 4.5 Рекурсивная оптимизация
  • 4.6 Теорема рекурсии
    • 4.6.1 Доказательство уникальности
• 5 В информатике
• 6 В биологии
• 7 В искусстве
• 8 См. Также
• 9 Ссылки
• 10 Библиография
• 11 Внешние ссылки

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

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

• Простой базовый вариант (или случаи) - сценарий завершения, который не использует рекурсию для получения ответа
• Рекурсивный шаг - набор правил, сокращающих все остальные случаи до ard the base case

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

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

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

$Fib\; (0)\; =\; 0\; как\; базовый\; случай\; 1,\; \{\backslash \; displaystyle\; \{\backslash \; text\; \{Fib\}\}\; (0)\; =\; 0\; \{\backslash \; text\; \{как\; базовый\; случай\; 1,\}\}\}$

$Fib\; (1)\; =\; 1\; как\; базовый\; случай\; 2,\; \{\backslash \; displaystyle\; \{\backslash \; text\; \{Fib\}\}\; (1)\; =\; 1\; \{\backslash \; text\; \{как\; базовый\; случай\; 2,\}\}\}$

$Для\; всех\; целых\; чисел\; n>1,\; Fib\; (n):\; =\; Fib\; (n\; -\; 1)\; +\; Фиб\; (n\; -\; 2).\; \{\backslash \; displaystyle\; \{\backslash \; text\; \{Для\; всех\; целых\; чисел\}\}\; n>1,\; ~\; \{\backslash \; text\; \{Fib\}\}\; (n):\; =\; \{\backslash \; text\; \{Fib\}\}\; (n-1)\; +\; \{\backslash \; text\; \{Fib\}\}\; (\; n-2).\}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A рекурсивная грамматика - это формальная грамматика, которая содержит рекурсивное производство rules.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Доказательства с использованием рекурсивных определений

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

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

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

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

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

$F\; (0)\; =\; a\; \{\backslash \; displaystyle\; F\; (0)\; =\; a\}$

$F\; (n\; +\; 1)\; =\; f\; (F\; (n))\; \{\backslash \; displaystyle\; F\; (n\; +\; 1)\; =\; f\; (F\; (n))\}$

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

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

Возьмем две функции $F:\; N\; \to \; X\; \{\backslash \; displaystyle\; F:\; \backslash \; mathbb\; \{N\}\; \backslash \; rightarrow\; X\}$и $G:\; N\; \to \; Икс\; \{\backslash \; displaystyle\; G:\; \backslash \; mathbb\; \{N\}\; \backslash \; rightarrow\; X\}$так, чтобы:

$F\; (0)\; =\; a\; \{\backslash \; displaystyle\; F\; (0)\; =\; a\}$

$G\; (0)\; знак\; равно\; a\; \{\backslash \; displaystyle\; G\; (0)\; =\; a\}$

$F\; (n\; +\; 1)\; =\; f\; (F\; (n))\; \{\backslash \; displaystyle\; F\; (n\; +\; 1)\; =\; f\; (F\; (n))\; \}$

$G\; (n\; +\; 1)\; =\; f\; (G\; (n))\; \{\backslash \; displaystyle\; G\; (n\; +\; 1)\; =\; f\; (G\; (n))\}$

, где a - элемент X.

С помощью математической индукции можно доказать, что $F\; (n)\; =\; G\; (n)\; \{\backslash \; displaystyle\; F\; (n)\; =\; G\; (n)\}$для всех натуральные числа n:

Базовый случай : $F\; (0)\; =\; a\; =\; G\; (0)\; \{\backslash \; displaystyle\; F\; (0)\; =\; a\; =\; G\; (0)\}$, поэтому равенство выполняется для $n\; =\; 0\; \{\backslash \; displaystyle\; n\; =\; 0\}$.

индуктивного шага : предположим, $F\; (k)\; =\; G\; (k)\; \{\backslash \; displaystyle\; F\; (k)\; =\; G\; (k)\; \}$для некоторого $k\; \in \; N\; \{\backslash \; displaystyle\; k\; \backslash \; in\; \backslash \; mathbb\; \{N\}\}$. Тогда $F\; (k\; +\; 1)\; =\; f\; (F\; (k))\; =\; f\; (G\; (k))\; =\; G\; (k\; +\; 1).\; \{\backslash \; Displaystyle\; 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)\; \{\backslash \; displaystyle\; F\; (n)\; =\; G\; (n)\}$для все $n\; \in \; N\; \{\backslash \; displaystyle\; n\; \backslash \; in\; \backslash \; mathbb\; \{N\}\}$.

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

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

unsigned int factorial (unsigned int n) {if (n == 0) {возврат 1; } else {вернуть n * факториал (n - 1); }}

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

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

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

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

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

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

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

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

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

• Corecursion
• Рекурсия курса значений
• Цифровая бесконечность
• Мечта во сне (стихотворение)
• Эффект Дросте
• Ложное пробуждение
• Комбинатор с фиксированной точкой
• Бесконечные композиции аналитических функций
• Бесконечный цикл
• Бесконечность
• Зеркало бесконечности
• Итерированная функция
• Математическая индукция
• Mise en abyme
• Реентерабельность (подпрограмма)
• Само-ссылка
• Spiegel im Spiegel
• Странная петля
• Хвостовая рекурсия
• Самореференционная формула Таппера
• Черепахи полностью вниз

1. ^«Аксиомы Пеано | математика». Британская энциклопедия. Проверено 24.10.2019.
2. ^«Окончательный глоссарий высшего математического жаргона - рекурсия». Математическое хранилище. 2019-08-01. Проверено 24.10.2019.
3. ^«Определение РЕКУРСИВНОГО». www.merriam-webster.com. Проверено 24 октября 2019 г.
4. ^Пинкер, Стивен (1994). Языковой инстинкт. Уильям Морроу.
5. ^Пинкер, Стивен; Джекендофф, Рэй (2005). «Факультет языка: что в нем такого особенного?». Познание. 95 (2): 201–236. CiteSeerX 10.1.1.116.7784. doi : 10.1016 / j.cognition.2004.08.004. PMID 15694646.
6. ^Нордквист, Ричард. «Что такое рекурсия в грамматике английского языка?». ThoughtCo. Проверено 24 октября 2019 г.
7. ^Невинс, Эндрю; Песецкий, Давид; Родригес, Силен (2009). «Доказательства и аргументация: ответ Эверетту (2009)» (PDF). Язык. 85 (3): 671–681. doi : 10.1353 / lan.0.0140. Архивировано из оригинального (PDF) 06.01.2012.
8. ^Друкер, Томас (4 января 2008 г.). Перспективы истории математической логики. Springer Science Business Media. п. 110. ISBN 978-0-8176-4768-1.
9. ^Барбара Парти и Матс Рут. 1983. В Rainer Bäuerle et al., Значение, использование и интерпретация языка. Перепечатано в книге Пола Портнера и Барбары Парти, ред. 2002. Формальная семантика: основные материалы. Блэквелл.
10. ^Недерхоф, Марк-Ян; Сатта, Джорджио (2002), «Анализ нерекурсивных контекстно-свободных грамматик», Труды 40-го ежегодного собрания Ассоциации компьютерной лингвистики (ACL '02), Страудсбург, Пенсильвания, США: Ассоциация компьютерной лингвистики, стр. 112– 119, doi : 10.3115 / 1073083.1073104.
11. ^ Хантер, Дэвид (2011). Основы дискретной математики. Джонс и Бартлетт. п. 494. ISBN 9781449604424.
12. ^«рекурсия - поиск Google». www.google.com. Проверено 24.10.2019.
13. ^«Картинка дня: фрактальная цветная капуста». Проверено 19 апреля 2020 года.
14. ^Танг, Дейзи. «Рекурсия». Проверено 24 сентября 2015 г. Еще примеры рекурсии: русские матрешки. Каждая кукла сделана из массива дерева или является полой и содержит внутри еще одну матрешку.
15. ^«Джотто ди Бондоне и помощники: триптих Стефанески». Ватикан. Проверено 16 сентября 2015 г.
16. ^Купер, Джонатан (5 сентября 2007 г.). «Искусство и математика». Проверено 5 июля 2020 г.

Викискладе есть медиафайлы, относящиеся к Рекурсия.

Искать рекурсия или рекурсивность в Wiktionary, бесплатном словаре.

• Рекурсия - учебник Алана Голда
• Zip Files All The Way Down
• Невинс, Эндрю и Давид Песецки и Силен Родригес. Доказательства и аргументация: ответ Эверетту (2009). Язык 85.3: 671-681 (2009)