20.Частично рекурсивные функции

Частично рекурсивная функция определяется аналогично примитивно рекурсивной, только к двум операторам суперпозиции (подстановки) и примитивной рекурсии добавляется ещё третий оператор - минимизации аргумента. Оператор минимизации аргумента. Пусть f - функция от n натуральных переменных. Тогда результатом применения оператора минимума аргумента к функции f называется функция h от n - 1 переменной, задаваемая следующим определением:

h (x1,…,xn-1) = min (y), при условии f (x1,…,xn-1,y) = 0.

То есть функция h возвращает минимальное значение последнего аргумента функции f, при котором её значение равно 0.

В терминах императивного программирования — примитивно рекурсивные функции соответствуют программным блокам, в которых используется только арифметические операции, а также условный оператор и оператор арифметического цикла (оператор цикла, в котором число итераций известно на момент начала цикла). Если же программист начинает использовать оператор цикла while, в котором число итераций заранее неизвестно, и в принципе, может быть бесконечным, то он переходит в класс частично рекурсивных функций.

Частично рекурсивные функции для некоторых значений аргумента могут быть не определены, так как оператор минимизации аргумента не всегда корректно определён, так как функция f может быть не равной нулю ни при каких значениях аргументов. С точки зрения императивного программирования, результатом частично рекурсивной функции может быть не только число, но и исключение или уход в бесконечный цикл, соответствующие неопределённому значению.