Рекурсивная функция (теория вычислимости): различия между версиями
| [отпатрулированная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
РоманСузи (обсуждение | вклад) оформление |
FeelUs (обсуждение | вклад) перенес императивную аналогию соответствующую примитивно-рекурсивным в соответствующий раздел |
||
Строка 31:
Множество '''примитивно рекурсивных функций''' — это минимальное множество, содержащее все базовые функции и замкнутое относительно указанных операторов подстановки и примитивной рекурсии.
В терминах [[Императивное программирование|императивного программирования]] — примитивно рекурсивные функции соответствуют программным блокам, в которых используется только арифметические операции, а также [[Оператор ветвления|условный оператор]] и оператор арифметического цикла ([[Цикл (программирование)|оператор цикла]], в котором число итераций известно на момент начала цикла). Если же программист начинает использовать оператор цикла <code>while</code>, в котором число итераций заранее неизвестно и, в принципе, может быть бесконечным, то он переходит в класс частично рекурсивных функций.▼
=== Примеры ===
Строка 59 ⟶ 61 :
: <math>h(x_1,\ldots, x_{n-1}) = \min y</math>, при условии <math>f(x_1,\ldots,x_{n-1},\,y)=0</math>
: То есть функция <math>h</math> возвращает минимальное значение последнего аргумента функции <math>f</math>, при котором её значение равно 0.
▲В терминах [[Императивное программирование|императивного программирования]] — примитивно рекурсивные функции соответствуют программным блокам, в которых используется только арифметические операции, а также [[Оператор ветвления|условный оператор]] и оператор арифметического цикла ([[Цикл (программирование)|оператор цикла]], в котором число итераций известно на момент начала цикла). Если же программист начинает использовать оператор цикла <code>while</code>, в котором число итераций заранее неизвестно и, в принципе, может быть бесконечным, то он переходит в класс частично рекурсивных функций.
Частично рекурсивные функции для некоторых значений аргумента могут быть не определены, так как оператор минимизации аргумента не всегда корректно определён, поскольку функция <math>f</math> может быть не равной нулю ни при каких значениях аргументов. С точки зрения императивного программирования, результатом частично рекурсивной функции может быть не только число, но и [[Исключение (программирование)|исключение]] или уход в бесконечный цикл, соответствующие неопределённому значению.
| |||