Рекурсия - Recursion

Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Рекурсия»  – Новости  · газеты  · книги  · ученый  · JSTOR (Июнь 2012 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

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

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

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

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

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

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

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

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

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

${displaystyle {ext {для всех целых чисел}} n> 1, ~ {ext {Fib}} (n): = {ext {Fib}} (n-1) + {ext {Fib}} (n-2). }$

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

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

Есть несколько ироничных определений рекурсии; видеть рекурсивный юмор.

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

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

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

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

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

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

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

На языке

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

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

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

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

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

А рекурсивная грамматика формальная грамматика, содержащая рекурсивные правила производства.^[10]

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

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

Рекурсия, см. Рекурсия.^[11]

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

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

Рекурсивные акронимы другие примеры рекурсивного юмора. PHP, например, означает "Препроцессор гипертекста PHP", ВИНО означает "WINE Is Not an Emulator" GNU означает "GNU не Unix", и SPARQL обозначает «Протокол SPARQL и язык запросов RDF».

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

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

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

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

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

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

если п в ${displaystyle mathbb {N}}$, тогда п +1 в ${displaystyle mathbb {N}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${displaystyle F (0) = a}$

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

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

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

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

${displaystyle F (0) = a}$

${displaystyle G (0) = a}$

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

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

куда а является элементом Икс.

Это может быть доказано математическая индукция который ${displaystyle F (n) = G (n)}$ для всех натуральных чисел п:

Базовый вариант: ${displaystyle F (0) = a = G (0)}$ так что равенство выполняется для ${displaystyle n = 0}$.

Индуктивный шаг: Предполагать ${displaystyle F (k) = G (k)}$ для некоторых ${displaystyle kin mathbb {N}}$. потом ${displaystyle F (k + 1) = f (F (k)) = f (G (k)) = G (k + 1).}$

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

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

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

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

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

беззнаковый int факториал(беззнаковый int п) {    если (п == 0) {        возвращаться 1;    } еще {        возвращаться п * факториал(п - 1);    }}

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

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

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

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

В биологии

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

В искусстве

Рекурсивные куклы: оригинальный набор Матрешки к Звездочкин и Малютин, 1892

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

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

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

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

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

Рекомендации

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

внешняя ссылка

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