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

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

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

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

0! = 1.

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

Это определение действительно для каждого натурального числа n , потому что рекурсия в конечном итоге достигает базового случая 0. Определение также можно рассматривать как процедуру для вычисления значения функции n !, начиная с n = 0 и продолжая дальше. с n = 1, n = 2, n = 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), и свойство выполняется для n +1, когда оно имеет значение n , тогда это свойство имеет место для всех натуральных чисел (Aczel 1977: 742).

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

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

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

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

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

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

Принцип рекурсивного определения [ править ]

Пусть быть множество , и пусть $0$ элемент из $A$ . Если $ρ$ - функция, которая присваивает каждой функции $f,$ отображающей непустую часть положительных целых чисел в $A$ , элемент $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 является базовым случаем; проверка простоты любого большего целого числа X по этому определению требует знания простоты каждого целого числа от 1 до X , что хорошо определяется этим определением. Последнее утверждение может быть доказано индукцией по X , для которой важно, чтобы во втором предложении говорилось «тогда и только тогда»; если бы было сказано просто «если», примитивность, например, 4 не была бы ясна, и дальнейшее применение второго предложения было бы невозможным.

Неотрицательные четные числа [ править ]

Эти цифры даже может быть определен как состоящий из

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

Правильно составленные формулы [ править ]

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

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

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

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

См. Также [ править ]

Математическая индукция
Рекурсивные типы данных
Рекурсия
Структурная индукция

Заметки [ править ]

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

Ссылки [ править ]

Халмос, Пол (1960). Теория наивных множеств . ван Ностранд . OCLC 802530334 .
Aczel, Питер (1977). «Введение в индуктивные определения». В Барвайз, Дж. (Ред.). Справочник по математической логике . Исследования по логике и основам математики. 90 . Северная Голландия . С. 739–782. DOI : 10.1016 / S0049-237X (08) 71120-0 . ISBN 0-444-86388-5.
Хайн, Джеймс Л. (2010). Дискретные структуры, логика и вычислимость . Джонс и Бартлетт . ISBN 978-0-7637-7206-2. OCLC 636352297 .

[1] "Окончательный словарь высшего математического жаргона - Рекурсия" . Математическое хранилище . 2019-08-01 . Проверено 24 октября 2019 .

[2] Хенкин, Леон (1960). «О математической индукции». Американский математический ежемесячник . 67 (4): 323–338. DOI : 10.2307 / 2308975 . ISSN 0002-9890 . JSTOR 2308975 .

[3] «Все о рекурсии» . www.cis.upenn.edu . Проверено 24 октября 2019 .

[4] Для доказательства теоремы рекурсии см. О математической индукции (1960) Леона Хенкина .

[Munkres-5] Манкрес, Джеймс (1975). Топология, первый курс (1-е изд.). Нью-Джерси: Прентис-Холл. п. 68, упражнения 10 и 12 . ISBN 0-13-925495-1.

[1]