Рекурсия

Процесс повторения предметов самоподобным образом

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

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

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

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

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

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

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

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

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

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

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

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

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

Многие математические аксиомы основаны на рекурсивных правилах. Например, формальное определение натуральных чисел аксиомами Пеано можно описать так: «Ноль — натуральное число, и каждое натуральное число имеет последователя, который также является натуральным числом». ^[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» Кернигана и Пайка. Его не было в первом издании The C Programming Language . Эта шутка является частью фольклора функционального программирования и была широко распространена в сообществе функционального программирования еще до публикации вышеупомянутых книг. ^{[12] [13]}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Функция может быть рекурсивно определена относительно самой себя . Знакомый пример — числовая последовательность Фибоначчи : 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)=a}$

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

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

Дедекинд был первым, кто поставил проблему однозначного определения теоретико-множественных функций с помощью рекурсии и дал набросок аргумента в эссе 1888 года «Was sind und was sollen die Zahlen?» ^[15] ${\displaystyle \mathbb {N} }$

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

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

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

${\displaystyle G(0)=a}$

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

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

где a — элемент 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 k\in \mathbb {N} }$

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

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

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

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

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

def  факториал ( n ):  если  n  >  0 :  вернуть  n  *  факториал ( n  -  1 )  иначе :  вернуть  1

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

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

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

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

В биологии

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

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

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

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

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

В бизнесе

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

В искусстве

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

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

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

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

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

В культуре

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

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

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

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

1. Кози, Роберт Л. (2006). Логика, множества и рекурсия (2-е изд.). Садбери, Массачусетс: Издательство Jones and Bartlett. ISBN 0-7637-3784-4. ОСЛК  62093042.
2. «Аксиомы Пеано | математика» . Британская энциклопедия . Проверено 24 октября 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. S2CID  1599505. 
6. Нордквист, Ричард. «Что такое рекурсия в английской грамматике?». МысльКо . Проверено 24 октября 2019 г.
7. Невинс, Эндрю; Песецкий, Дэвид; Родригес, Силин (2009). «Доказательства и аргументация: ответ Эверетту (2009)» (PDF) . Язык . 85 (3): 671–681. дои : 10.1353/lan.0.0140. S2CID  16915455. Архивировано из оригинала (PDF) 6 января 2012 г.
8. Друкер, Томас (4 января 2008 г.). Перспективы истории математической логики. Springer Science & Business Media. п. 110. ИСБН 978-0-8176-4768-1.
9. Барбара Парти и Матс Рут. 1983. Райнер Бойерле и др., Значение, использование и интерпретация языка . Перепечатано в книге Пола Портнера и Барбары Парти, ред. 2002. Формальная семантика: основные материалы для чтения . Блэквелл.
10. Недерхоф, Марк-Ян; Сатта, Джорджио (2002), «Разбор нерекурсивных бесконтекстных грамматик», Труды 40-го ежегодного собрания Ассоциации компьютерной лингвистики (ACL '02) , Страудсбург, Пенсильвания, США: Ассоциация компьютерной лингвистики, стр. 112– 119, дои : 10.3115/1073083.1073104.
11. Хантер, Дэвид (2011). Основы дискретной математики. Джонс и Бартлетт. п. 494. ИСБН 9781449604424.
12. Шаффер, Эрик. «CS 173: Дискретные структуры» (PDF) . Университет Иллинойса в Урбана-Шампейн . Проверено 7 июля 2023 г.
13. «Введение в информатику и программирование на C; Сессия 8: 25 сентября 2008 г.» (PDF) . Колумбийский университет . Проверено 7 июля 2023 г.
14. "рекурсия - Поиск в Google" . www.google.com . Проверено 24 октября 2019 г.
15. А. Канамори, «Похвала замене», стр. 50–52. Бюллетень символической логики, вып. 18, нет. 1 (2012). По состоянию на 21 августа 2023 г.
16. «Картина дня: фрактальная цветная капуста». 28 декабря 2012 года . Проверено 19 апреля 2020 г.
17. Бурдье, Пьер (1992). «Двойная связка и преобразование». Для рефлексивной антропологии . Париж: Ле Сёй.
18. Гидденс, Энтони (1987). Социальная теория и современная социология . Политическая пресса.
19. Алехандро, Одри (2021). «Рефлексивный дискурс-анализ: методология практики рефлексивности». Европейский журнал международных отношений . 27 (1): 171. дои : 10.1177/1354066120969789 . ISSN  1354-0661. S2CID  229461433.
20. «Интерфейс канадского малого бизнеса и банка: рекурсивная модель». Журналы SAGE.
21. Пиво, Стаффорд (1972). Мозг фирмы . ISBN 978-0471948391.
22. Тан, Дейзи. «Рекурсия» . Проверено 24 сентября 2015 г. Еще примеры рекурсии: Русские матрешки. Каждая кукла изготовлена ​​из цельного дерева или полая и содержит внутри еще одну матрешку.
23. «Джотто ди Бондоне и помощники: триптих Стефанески». Ватикан . Проверено 16 сентября 2015 г.
24. Свозил, Карл (2018). Физическая (А) причинность: детерминизм, случайность и беспричинные события. Спрингер. п. 12. ISBN 9783319708157.
25. Купер, Джонатан (5 сентября 2007 г.). «Искусство и математика» . Проверено 5 июля 2020 г.
26. "-ception - База данных неологизмов Университета Райса" . Университет Райса. Архивировано из оригинала 5 июля 2017 года . Проверено 23 декабря 2016 г.

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

• Дейкстра, Эдсгер В. (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)