Рекурсивное определение - Recursive definition

Четыре этапа строительства Коха снежинка. Как и многие другие фракталы, этапы получаются с помощью рекурсивного определения.

В математика и Информатика, а рекурсивное определение, или же индуктивное определение, используется для определения элементы в набор по другим элементам в наборе (Aczel 1977: 740 и далее). Некоторые примеры рекурсивно определяемых объектов включают факториалы, натуральные числа, Числа Фибоначчи, а Троичный набор Кантора.^[1]

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

0! = 1.

(п + 1)! = (п + 1)·п!.

Это определение действительно для каждого натурального числа п, потому что рекурсия в конечном итоге достигает базовый вариант of 0. Определение также можно рассматривать как процедуру для вычисления значения функциип!, начиная с п = 0 и продолжая дальше с п = 1, п = 2, п = 3 и т. Д.

Теорема рекурсии утверждает, что такое определение действительно определяет уникальную функцию. Доказательство использует математическая индукция.^[2]

Индуктивное определение набора описывает элементы набора в терминах других элементов набора. Например, одно определение набора N из натуральные числа является:

1 находится в N.
Если элемент п в N тогда п +1 в N.
N является пересечением всех множеств, удовлетворяющих (1) и (2).

Есть много наборов, которые удовлетворяют (1) и (2) - например, набор {1, 1.649, 2, 2.649, 3, 3.649, ...} удовлетворяет определению. Однако условие (3) определяет набор натуральных чисел, удаляя наборы с посторонними элементами. Обратите внимание, что это определение предполагает, что N содержится в большом наборе (таком как набор действительных чисел), в котором определена операция +.

Свойства рекурсивно определенных функций и множеств часто можно доказать с помощью принципа индукции, который следует рекурсивному определению. Например, определение натуральных чисел, представленное здесь, непосредственно подразумевает принцип математической индукции для натуральных чисел: если свойство имеет место для натурального числа 0 (или 1), и свойство имеет место п+1 всякий раз, когда он содержит п, то свойство выполняется для всех натуральных чисел (Aczel 1977: 742).

Форма рекурсивных определений

Большинство рекурсивных определений имеют две основы: базовый случай (базис) и индуктивное предложение.

Разница между круговое определение и рекурсивное определение состоит в том, что рекурсивное определение всегда должно иметь базовые случаи, случаи, удовлетворяющие определению без определены в терминах самого определения, и что все другие экземпляры в индуктивных предложениях должны быть в некотором смысле «меньше» (т. е. ближе к тем базовым случаям, которые завершают рекурсию) - правило, также известное как «повторять только в более простом случае».^[3]

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

То, что рекурсивные определения действительны, то есть рекурсивное определение идентифицирует уникальную функцию, является теоремой теории множеств, известной как теорема рекурсии, доказательство которого нетривиально.^[4] Если областью определения функции являются натуральные числа, достаточными условиями для допустимости определения является то, что значение ${ displaystyle f (0)}$ (т.е. базовый случай), а для п > 0 приведен алгоритм определения ${ Displaystyle f (п)}$ с точки зрения ${ Displaystyle п, е (0), е (1), ldots, е (п-1)}$ (т.е. индуктивное предложение).

В более общем смысле, рекурсивные определения функций могут быть сделаны всякий раз, когда домен является упорядоченный набор, используя принцип трансфинитная рекурсия. Формальные критерии того, что составляет действительное рекурсивное определение, в общем случае более сложны. Набросок общего доказательства и критериев можно найти в Джеймс Мункрес ' Топология. Однако конкретный случай (домен ограничен положительными целые числа вместо любого упорядоченного множества) общего рекурсивного определения будет дано ниже.^[5]

Принцип рекурсивного определения

Позволять ${ displaystyle A}$ быть набором и пусть ${ displaystyle a_ {0}}$ быть элементом ${ displaystyle A}$ . Если ${ displaystyle rho}$ это функция, которая присваивает каждой функции ${ displaystyle f}$ отображение непустой части натуральных чисел в ${ displaystyle A}$ , элемент ${ displaystyle A}$ , то существует единственная функция ${ displaystyle h: mathbb {Z} _ {+} to A}$ такой, что

{ displaystyle h (1) = a_ {0}}

{ displaystyle h (i) = rho (h | _ { {1,2, ldots, i-1 }}) { text {for}} i> 1.}

Примеры рекурсивных определений

Элементарные функции

Дополнение определяется рекурсивно на основе подсчета

{ Displaystyle 0 + а = а,}

{ displaystyle (1 + n) + a = 1 + (n + a).}

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

{ displaystyle 0a = 0,}

{ displaystyle (1 + n) a = a + na.}

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

{ displaystyle a ^ {0} = 1,}

{ displaystyle a ^ {1 + n} = aa ^ {n}.}

Биномиальные коэффициенты можно определить рекурсивно как

{ displaystyle { binom {a} {0}} = 1,}

{ displaystyle { binom {1 + a} {1 + n}} = { frac {(1 + a) { binom {a} {n}}} {1 + n}}.}

простые числа

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

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

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

Неотрицательные четные числа

В четные числа можно определить как состоящий из

0 находится в наборе E неотрицательных событий (базовая оговорка),
Для любого элемента Икс в наборе E, Икс + 2 в E (индуктивная оговорка),
Ничего нет в E если он не получен из базисных и индуктивных предложений (экстремальные предложения).

Хорошо сформированные формулы

Рекурсивные определения находятся в основном в логике или компьютерном программировании. Например, правильно сформированная формула (wff) можно определить как:

символ, обозначающий предложение - подобно п означает «Коннор - юрист».
Символ отрицания, за которым следует wff - вроде Np означает: «Неправда, что Коннор - юрист».
Любой из четырех двоичных связки (C, А, K, или же E) с последующими двумя wffs. Символ K означает "оба верны", поэтому Kpq может означать «Коннор - юрист, а Мэри любит музыку».

Ценность такого рекурсивного определения состоит в том, что его можно использовать для определения того, является ли какая-либо конкретная строка символов «правильно сформированной».

Kpq хорошо сформирован, потому что это K а затем атомные wffs п и q.
НКпк хорошо сформирован, потому что это N с последующим Kpq, который, в свою очередь, является wff.
KNpNq является K с последующим Np и Nq; и Np это wff и т. д.

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

Примечания

^ "Окончательный словарь высшего математического жаргона - Рекурсия". Математическое хранилище. 2019-08-01. Получено 2019-10-24.
^ Хенкин, Леон (1960). «О математической индукции». Американский математический ежемесячник. 67 (4): 323–338. Дои:10.2307/2308975. ISSN 0002-9890. JSTOR 2308975.
^ "Все о рекурсии". www.cis.upenn.edu. Получено 2019-10-24.
^ Для доказательства теоремы о рекурсии см. О математической индукции (1960) Леона Хенкина.
^ Мункрес, Джеймс (1975). Топология, первый курс (1-е изд.). Нью-Джерси: Прентис-Холл. п.68, упражнения 10 и 12. ISBN 0-13-925495-1.