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

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

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

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

0! = 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть быть множество , и пусть ₀ элемент из 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) может быть определена как:

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

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

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

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

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

Примечания

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

• Халмос, Пол (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 .