Рекурсия - Recursion

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

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

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

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

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

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

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

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

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

Fib (0) = 0 как базовый случай 1,

Fib (1) = 1 как базовый случай 2,

Для всех целых чисел п > 1 , Фибо ( п ) = Fib ( п - 1) + Fib ( п - 2) .

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

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

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

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

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

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

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

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

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

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

На языке

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

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

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

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

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

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

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

Рекурсивная страница Википедии

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

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

Вариант можно найти на странице 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».

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\ Displaystyle F (0) = а}$

${\ Displaystyle F (n + 1) = f (F (n))}$

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

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

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

${\ Displaystyle F (0) = а}$

${\ Displaystyle G (0) = а}$

${\ Displaystyle F (n + 1) = f (F (n))}$

${\ Displaystyle G (п + 1) = е (G (п))}$

где является элементом X .

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

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

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

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

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

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

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

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

unsigned int factorial(unsigned int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

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

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

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

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

В биологии

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

В искусстве

Рекурсивные куклы: оригинальный набор матрешки по Zvyozdochkin и Малютин , 1892 г.

Передняя поверхность Giotto «s Stefaneschi Триптих , 1320, рекурсивно содержит образ себя (держится на коленах фигуры в центральной панели).

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

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

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

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

использованная литература

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

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

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