МНОГОКРАТНАЯ РЕКУРСИЯ

- вид рекурсии, в к-рой участвуют сразу несколько переменных. Наборы значений этих переменных упорядочиваются лексикографически. Под это определение подходят многочисленные конкретные рекурсивные описания. Если в таком описании искомая функция не подставляется сама в себя, то оно сводится к примитивной рекурсии. В общем случае М. р. выводит за рамки примитивно рекурсивных функций, т. к. посредством двукратной рекурсии (ведущейся по двум переменным) можно построить функцию, универсальную для примитивно рекурсивных функций (аналогично, для k-рекурсивных функций существует (k+1 )(-кратная универсальная функция). Всевозможные разновидности k-кратной рекурсии можно свести к следующей нормальной форме:

Лит.:[1] Петер Р., Рекурсивные функции, пер. с нем., М., 1954.

Н. В. Белякин.