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


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

40 ; РЕКУРСИВНЫЕ ФУНКЦИИ ' -
3) Определение числа сочетаний, из п элементов по а в п. 23,
=*<«>.
где а — не рекурсивное переменное, но и не неизменный параметр, ибо на место а подставляется а— 1.
4) Определение наибольшего общего делителя в п. 21:
dv(0, n)=n, dv(m+l,0)=m+l, dv(m+l,n + 1) = sg(n— m) dv(m— n, n+l)+ (n— m)dv(m + l, n— m),
где рекурсия производится одновременно по обоим переменным, т. е. значение функции в точке (т-{-1, п 4-1) вычисляется через значения функции в таких точках, где либо значение первой координаты, либо (при неизменной первой) значение второй уменьшено.
ч Тем не менее, в следующих параграфах мы установим, что эти четыре рекурсии, не являющиеся примитивными, сводятся к примитивным рекурсиям и подстановкам. Таким образом, при определении наиболее употребительных функций элементарной теории чисел можно ограничиться примитивными рекурсиями.
4. В § 1 при определении функций нам часто приходилось учитывать различные случаи, соответственно тому, какое отношение имеет место между аргументами. Например, в п. 4 при определении
п
2а(*'»а1>"->аг) различались случаи т>п, т=0, 0<тг<п. Эти от-
i—m
ношения были в п. 5 охарактеризованы посредством «характеристических функций» {^(/n, n), P2(m, п), Рз(т, п). Каждая из этих функций принимает значение 1, когда для аргументов выполняется соответствующее отношение, и 0 в противном случае. Перечисленные отношения можно, однако, с тем же успехом охарактеризовать функциями
sg(PM «)), sg(p2(m,n)) и sg(ps(/n, n)),
каждая из которых обращается в 0 тогда и только тогда, когда имеет место соответствующее отношение между тип.
Отношения будем всегда1 обозначать большими греческими буквами. Отношение В(а1,...,аг) называется рекурсивным, если существует рекурсивная функция р (av . . . , аг), обращающаяся в 0 тогда и только тогда, когда а^..., аг удовлетворяют, отношению В. Если

 

1 10 20 30 40 41 42 43 44 45 46 47 48 49 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260


Математика