Другие виды рекурсии

Слова " рекурсивное определение функции" можно понимать и в более широком смысле, нежели мы это делали (см. выше определение рекурсии, или примитивной рекурсии) как любой способ задания функции, который связывает значение функции в данной точке с другими ее значениями. Как мы увидим ниже при обсуждении функции Аккермана, есть такие схемы рекурсивных определений, которые выводят из класса примитивно рекурсивных функций. Но есть и такие, которые можно свести к рассмотренной нами схеме.

Мы приведем два примера последнего типа: совместное определение нескольких функций и использование произвольных меньших значений аргумента.

Совместная рекурсия. Пусть две одноместные функции f и g заданы соотношениями:

f(0) = a,

g(0) = b,

f(n+1) = F(n,f(n),g(n)),

g(n+1) = G(n,f(n),g(n)),

где a и b некоторые числа, а функции F и G примитивно рекурсивные функции трех аргументов. Покажем, что тогда функции f и g примитивно рекурсивны.

Чтобы доказать это, нам потребуется примитивно рекурсивная нумерация пар такая функция (номер пары мы обозначаем квадратными скобками), которая была бы примитивно рекурсивна вместе с двумя обратными функциями (дающими по номеру пары ее первый и второй члены). Тогда мы сможем написать рекурсивное определение для функции h(n)=[f(n),g(n)]:

h(0) = [a,b],

h(n+1) = [F(n,p₁(h(n)),p₂(h(n))),G(n,p₁(h(n)),p₂(h(n)))],

где функции p₁ и p₂ дают по номеру пары первый и второй ее члены. Если функция h примитивно рекурсивна, то и функции f и g (композиции h с функциями p₁ и p₂ ) также примитивно рекурсивны.

Осталось объяснить, как найти примитивно рекурсивную нумерацию пар. Можно заметить, что есть многочлен второго порядка с двумя переменными, задающий взаимно однозначное соответствие N x N -> N. Это соответствие видно из таблицы:

3 7

1 4 8

0 2 5 9

Примитивную рекурсивность обратных отображений p₁ и p₂ можно установить, воспользовавшись ограниченной минимизацией, так как p₁(n) есть минимальное x <= n, для которого найдется y <= n, при котором [x,y]=n.

Менее симметричная нумерация пар может быть задана формулой [a,b]=(2a+1)2^b-1. Можно также заметить, что нам не нужно, чтобы все числа были номерами каких-то пар, и воспользоваться нумерацией [a,b]=2^a3^b.

Заметим в заключение, что аналогичная конструкция применима для большего числа одновременно определяемых функций и для функций от большего числа аргументов.

Возвратная рекурсия. Следующее утверждение показывает, что при рекурсивном определении можно использовать не только значение в предыдущей точке, но и любое предшествующее значение.

Теорема 74. Пусть функция g одного аргумента примитивно рекурсивна, причем g(x)<x при x>0 ; пусть F примитивно рекурсивная функция двух аргументов; пусть c произвольная константа. Тогда функция h, определенная соотношениями

h(0) = c,

h(x) = F(x,h(g(x))) при x>0

примитивно рекурсивна.

Чтобы доказать эту теорему, используем следующую нумерацию конечных последовательностей натуральных чисел: номером пустой последовательности считаем число 1, номером одноэлементной последовательности считаем число 2^a+1, последовательность имеет номер 2^a+13^b+1, последовательность имеет номер 2^a+13^b+15^c+1 и так далее (основания степеней простые числа). Будем обозначать номер последовательности через [a,b,...,z]. Эта нумерация в некотором смысле примитивно рекурсивна. Конечно, буквально это понимать нельзя, так как нумерация представляет собой " функцию с переменным числом аргументов". Но разные связанные с ней функции примитивно рекурсивны. В частности, таковы функции

• Length(x) = длина последовательности с номером x ;
• Select(i,x)=i -ый член последовательности с номером x ;
• Append(x,y)= номер последовательности, которая получается приписыванием числа y к последовательности с номером x.

Все эти функции (и другие аналогичные) сводятся к различным операциям с простыми числами и множителями, которые мы в сущности уже разбирали.

Теперь мы докажем, что функция

примитивно рекурсивна. В самом деле, H(0)=[c], а

H(k+1)= Append(H(k),F(k+1,Select(g(k+1),H(k)))).

Задание.

1. “Задача о коровах”

Есть два утверждения:

1) три коровы — это стадо коров;

2) стадо из n > 3 коров — это стадо из n – 1 коровы и еще одна корова,

— о которых можно сказать, что это — рекурсивное определение понятия “стадо коров”.

Необходимо, используя это определение, проверить, является ли стадом группа из пяти коров (обозначим ее К5).

2. Рекурсивная функция для расчета факториала заданного числа n: