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

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

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

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

В противоположность этому циклическое определение не имеет базовых случаев и определяет себя в терминах себя, а не в виде версии себя, более близкой к базовому классу. Это ведёт к порочному кругу . Таким образом, шутка типа "Рекурсивное определение: см. Рекурсивное определение " некорректна: на самом деле это циклическое определение.

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

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

Простые числа могут быть определены как:

  • 2 , наименьшее простое;
  • каждое положительное число, которое не делится ни на одно из простых меньше себя.

Целое число 2 — это наш базовый случай; проверка простоты любого большего числа X требует от нас знания простоты каждого целого между X и 2, но каждое такое число ближе к базовому случаю 2, нежели X.

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

Чётные числа могут быть определены, как состоящие из

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

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

Примеры:

  • GNU означает «GNU (is) Not Unix» (или "GNU’s Not Unix").
  • PHP расшифровывается как «PHP: Hypertext Preprocessor»
  • YAML - «YAML Ain't Markup Language »

См. также

Источник —

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