 | Эту страницу предлагается объединить со страницей Рекурсия. |
Рекурсивное определение или индуктивное определение определяет сущность в терминах её самой (то есть рекурсивно), хотя и полезным способом. Для того, чтобы это было возможно, определение в любом данном случае должно быть хорошо-основанным, избегая бесконечной регрессии.
Большинство рекурсивных определений имеют три основы: базис, индуктивное выражение и экстремальное выражение.
Разница между циклическим определением и рекурсивным определением состоит в том, что последнее должно иметь базовые случаи, которые удовлетворяют определению без того, чтобы быть определяемыми в терминах самого определения, и все другие случаи, охваченные определением, должны быть "меньше" (ближе к тем базовым случаям, которые прерывают рекурсию).
В противоположность этому циклическое определение не имеет базовых случаев и определяет себя в терминах себя, а не в виде версии себя, более близкой к базовому классу. Это ведёт к порочному кругу. Таким образом, шутка типа "Рекурсивное определение: см. Рекурсивное определение" некорректна: на самом деле это циклическое определение.
Примеры рекурсивных определений
Простые числа
Простые числа могут быть определены как:
- 2, наименьшее простое;
- каждое положительное число, которое не делится ни на одно из простых меньше себя.
Целое число 2 — это наш базовый случай; проверка простоты любого большего числа X требует от нас знания простоты каждого целого между X и 2, но каждое такое число ближе к базовому случаю 2, нежели X.
Неотрицательные чётные числа
Чётные числа могут быть определены, как состоящие из
- 0 во множестве N неотрицательных чётных (базовое выражение)
- Для любого элемента x во множестве N, x+2 тоже в N (индуктивное выражение)
- В N находятся только те элементы, которые получены из базового и индуктивного выражения (экстремальное выражение)
Рекурсивные определения в информатике
Примеры:
См. также
 | Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .