Рекурсия

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

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

Рекурсия возникает, когда определение понятия или процесса зависит от более простой или предыдущей версии самого себя. ^[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]

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

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

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

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

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

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

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

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

Рекурсивные аббревиатуры — еще один пример рекурсивного юмора. Например, PHP означает «PHP Hypertext Preprocessor», WINE означает «WINE Is Not an Emulator», GNU означает «GNU's not Unix», а SPARQL означает «SPARQL Protocol and RDF Query Language».

В математике

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

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

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

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

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  factorial ( n ):  если  n  >  0 :  вернуть  n  *  factorial ( 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]

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

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

Ссылки

1. Коуси, Роберт Л. (2006). Логика, множества и рекурсия (2-е изд.). Садбери, Массачусетс: Jones and Bartlett Publishers. ISBN 0-7637-3784-4. OCLC  62093042.
2. "Аксиомы Пеано | математика". Encyclopedia Britannica . Получено 24.10.2019 .
3. "Определение РЕКУРСИВНОГО". www.merriam-webster.com . Получено 24.10.2019 .
4. Пинкер, Стивен (1994). Языковой инстинкт . Уильям Морроу.
5. Пинкер, Стивен; Джекендофф, Рэй (2005). «Способность языка: что в ней особенного?». Cognition . 95 (2): 201–236. CiteSeerX 10.1.1.116.7784 . doi :10.1016/j.cognition.2004.08.004. PMID  15694646. S2CID  1599505. 
6. Нордквист, Ричард. «Что такое рекурсия в английской грамматике?». ThoughtCo . Получено 24.10.2019 .
7. Nevins, Andrew; Pesetsky, David; Rodrigues, Cilene (2009). «Доказательства и аргументация: ответ Эверетту (2009)» (PDF) . Язык . 85 (3): 671–681. doi :10.1353/lan.0.0140. S2CID  16915455. Архивировано из оригинала (PDF) 2012-01-06.
8. Друкер, Томас (4 января 2008 г.). Перспективы истории математической логики. Springer Science & Business Media. стр. 110. ISBN 978-0-8176-4768-1.
9. Барбара Парти и Матс Рут. 1983. В Rainer Bäuerle et al., Значение, использование и интерпретация языка . Перепечатано в Paul Portner and Barbara Partee, eds. 2002. Formal Semantics: The Essential Readings . Blackwell.
10. Недерхоф, Марк-Ян; Сатта, Джорджио (2002), «Анализ нерекурсивных контекстно-свободных грамматик», Труды 40-го ежегодного собрания Ассоциации компьютерной лингвистики (ACL '02) , Страудсбург, Пенсильвания, США: Ассоциация компьютерной лингвистики, стр. 112–119, doi : 10.3115/1073083.1073104.
11. Хантер, Дэвид (2011). Основы дискретной математики. Джонс и Бартлетт. стр. 494. ISBN 9781449604424.
12. Шаффер, Эрик. "CS 173: Дискретные структуры" (PDF) . Иллинойсский университет в Урбане-Шампейне . Получено 7 июля 2023 г. .
13. "Введение в информатику и программирование на языке C; Сессия 8: 25 сентября 2008 г." (PDF) . Колумбийский университет . Получено 7 июля 2023 г. .
14. "рекурсия - Поиск Google". www.google.com . Получено 2019-10-24 .
15. А. Канамори, «В похвалу замене», стр. 50–52. Бюллетень символической логики, т. 18, № 1 (2012). Доступ 21 августа 2023 г.
16. "Картинка дня: Фрактальная цветная капуста". 28 декабря 2012 г. Получено 19 апреля 2020 г.
17. Бурдье, Пьер (1992). «Двойная связка и преобразование». Для рефлексивной антропологии . Париж: Ле Сёй.
18. Гидденс, Энтони (1987). Социальная теория и современная социология . Polity Press.
19. Алехандро, Одри (2021). «Рефлексивный дискурсивный анализ: методология практики рефлексивности». Европейский журнал международных отношений . 27 (1): 171. doi : 10.1177/1354066120969789 . ISSN  1354-0661. S2CID  229461433.
20. «Канадский малый бизнес–банковский интерфейс: рекурсивная модель». Журналы SAGE.
21. Бир, Стаффорд (1972). Мозг фирмы . ISBN 978-0471948391.
22. Тан, Дейзи. "Рекурсия" . Получено 24 сентября 2015 г. Еще примеры рекурсии: Русские матрешки. Каждая кукла сделана из цельного дерева или полая и содержит внутри себя другую матрешку.
23. "Джотто ди Бондоне и помощники: триптих Стефанески". Ватикан . Получено 16 сентября 2015 г.
24. Свозил, Карл (2018). Физическая (А)причинность: детерминизм, случайность и беспричинные события. Springer. стр. 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). Дискретная математика . Prentice Hall. ISBN 978-0-13-117686-7.
• Хофштадтер, Дуглас (1999). Гёдель, Эшер, Бах: вечная золотая коса. Базовые книги. ISBN 978-0-465-02656-2.
• Шенфилд, Джозеф Р. (2000). Теория рекурсии . AK Peters Ltd. ISBN 978-1-56881-149-9.
• Коуси, Роберт Л. (2001). Логика, множества и рекурсия . Джонс и Бартлетт. ISBN 978-0-7637-1695-0.
• Cori, Rene; Lascar, Daniel; Pelletier, Donald H. (2001). Теория рекурсии, Теоремы Гёделя, Теория множеств, Теория моделей . Oxford University Press. ISBN 978-0-19-850050-6.
• Барвайз, Джон ; Мосс, Лоуренс С. (1996). Порочные круги . Центр Стэнфордского университета по изучению языка и информации. ISBN 978-0-19-850050-6. - предлагает обработку корекурсии .
• Розен, Кеннет Х. (2002). Дискретная математика и ее приложения . McGraw-Hill College. ISBN 978-0-07-293033-7.
• Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001). Введение в алгоритмы . Мит Пр. ISBN 978-0-262-03293-3.
• Керниган, Б.; Ритчи, Д. (1988). Язык программирования C. Prentice Hall. 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)