Рекурсивная функция (теория вычислимости): различия между версиями

перенес императивную аналогию соответствующую примитивно-рекурсивным в соответствующий раздел
(оформление)
(перенес императивную аналогию соответствующую примитивно-рекурсивным в соответствующий раздел)
 
Множество '''примитивно рекурсивных функций''' — это минимальное множество, содержащее все базовые функции и замкнутое относительно указанных операторов подстановки и примитивной рекурсии.
 
В терминах [[Императивное программирование|императивного программирования]] — примитивно рекурсивные функции соответствуют программным блокам, в которых используется только арифметические операции, а также [[Оператор ветвления|условный оператор]] и оператор арифметического цикла ([[Цикл (программирование)|оператор цикла]], в котором число итераций известно на момент начала цикла). Если же программист начинает использовать оператор цикла <code>while</code>, в котором число итераций заранее неизвестно и, в принципе, может быть бесконечным, то он переходит в класс частично рекурсивных функций.
 
=== Примеры ===
: <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> может быть не равной нулю ни при каких значениях аргументов. С точки зрения императивного программирования, результатом частично рекурсивной функции может быть не только число, но и [[Исключение (программирование)|исключение]] или уход в бесконечный цикл, соответствующие неопределённому значению.