11.2. Примеры примитивно рекурсивных функций

Как и с другими вычислительными моделями, важно накопить некоторый программистский опыт.

Сложение. Функция (х,у) I—У ашп(х, у) = х + у получа­ется с помощью рекурсии:

ашп(х, 0) = х; ахш\(х, у + 1) = ахш\(х, у) + 1.

Надо, конечно, представить правую часть второго ра­венства как результат подстановки. Формально говоря, к(х,у,г) в определении рекурсии надо положить рав­ным в(г), где в — функция прибавления единицы.

Умножение. Функция (х,у) I—У ргос1(х,у) = ху получа­ется с помощью рекурсии (с использованием сложения):

ргос1(а:,0) = 0; ргосЦш, у + 1) = ргос!(а:, у) + х.

Аналогичным образом можно перейти от умножения к возведению в степень.

Усечённое вычитание. Мы говорим об «усечённом вы­читании» х — у = х — у при х^ужх — у = 0 при х < у, поскольку мы имеем дело только с натуральными (целы­ми неотрицательными) числами. Одноместная функция усечённого вычитания единицы определяется рекурсив­но:

0-1 = 0;

(У + 1) - 1 = У-

(Рекурсия здесь формальна, так как предыдущее значе­ние не используется.) После этого усечённое вычитание для произвольных аргументов можно определить так:

х — 0 = х; Ж — (у + 1) = (ж — у) — 1.