Многократная рекурсия

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