Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Петер Р.N. Рекурсивные функции
 
djvu / html
 

100 РЕКУРСИВНЫЕ ФУНКЦИИ
и (при п>0)
|а(ф(ехр,(я),а)), если ехр0(п)=0, Ф(»• а)=Шехрл (я), ф (ехра(га), а)), если ехр0 (я) = 1,
h (ехра (п), «[> (expa(tt), а), <|» (ехр8(п), а)) в остальных случаях.
Это некоторая возвратная рекурсия, которая сводится к примитивной рекурсии и подстановке методом, изложенным в§ 3. А через ф(га,а) можно выразить значения <р(1,а), <р(2, а), <р(3, а),..., которые входят в число «звеньев» построения fy(n, а). Точнее говоря, как и в
случае <р(п, а)=( л ) в § 5, можно построить такую примитивно-
\в/ рекурсивную функцию х(п), для которой
<р(я,а)=ф(х(я),а).
Отсюда видно, что и <р(п, а) оказывается примитивно-рекурсивной. Аналогично показывается1), что и гораздо более сложные однократные рекурсии со вставками не выводят за пределы класса примитивно-рекурсивных функций.
3. Если этот же прием попытаться применить к двукратным и вообще к пробегающим по многим переменным «многократным» рекурсиям, то он не принесет желаемых результатов, и это не случайно: как мы знаем, многократная рекурсия со вставками выводит за' пределы класса примитивно-рекурсивных функций. Позднее будет показано, что в определении функции <|», значениями которой служат «звенья» построения некоторой функции, заданной многократной рекурсией со вставками, обязательно должны встречаться вставленные друг в друга значения <|>. Тем не менее, попытка применить указанный прием к многократным рекурсиям не бесполезна: таким путем весьма сложные определения со вставками можно свести к более простым, в которых встречаются лишь одинарные вставки.
4. Мы получим дальнейшее упрощение многократной рекурсии, если заметим, что «начальное значение» (т. е. значение функции, когда один из аргументов равен 0) можно выбирать произвольно; в частности, в качестве этого значения можно принять 0 или 12). Покажем, как провести редукцию к рекурсии с так «нормированным» начальным значением, на примере рассмотренной в начале этого параграфа двукратной рекурсии
______ ф(0,я)=я+1,
») Доказательство можно найти в работах Петер [2] и [4]. *) Петер [5], § 1.

 

1 10 20 30 40 50 60 70 80 90 100 101 102 103 104 105 106 107 108 109 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260


Математика