28.Понятие рекурсии. Примитивно-рекурсивные функции. Примеры.

Рекурсивным называется объект, частично состоящий или определяемый с помощью самого себя. Факториал — это классический пример рекурсивного объекта. Факториал числа п — это произведение целых чисел от 1 до п. Обозначается факториал числа п так: n!.

Согласно определению

n! = 1 х 2 х 3 х ... х (п - 1) х п. Приведенное выражение можно переписать так:

n! = nх ((n - 1) х (n - 2) х ...х 3 х 2 х 1) = n х (n - 1)!

То есть, факториал числа п равен произведению числа п на факториал числа (п - 1). В свою очередь, факториал числа («-!) — это произведение числа (п - 1) на факториал числа (п - 2) и т. д.

Таким образом, если вычисление факториала п реализовать как функцию, то в теле этой функции будет инструкция вызова функции вычисления факториала числа (п - 1), т. е. функция будет вызывать сама себя. Такой способ вызова называется рекурсией, а функция, которая обращается сама к себе, называется рекурсивной функцией.

Примитивно рекурсивными называют функции, которые можно получить с помощью операций подстановки и рекурсии из следующих базисных функций: константы 0, операции прибавления единицы s : x   x+1 и семейства функций проекции: это семейство для каждого k содержит k штук k -местных функций  .

Функции проекции позволяют выполнять " неоднородные" подстановки: скажем, можно получить функцию   из функций f и h, комбинируя их с функциями проекции: сначала получаем функцию   (подстановка   в g ), затем   (подстановка   в h ), затем полученные две функции вместе с функцией   подставляем в f.

Подставляя константу 0 в функцию прибавления единицы, получаем константу (функцию нуля аргументов) 1. Затем можно получить константы 2, 3 и т.д.

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

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

Сложение. Функция   получается с помощью рекурсии:

sum(x,0)=x;

sum(x,y+1)=sum(x,y)+1.

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

Умножение. Функция   получается с помощью рекурсии (с использованием сложения):

prod(x,0)=0;

prod(x,y+1)=prod(x,y)+x.

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

Усеченное вычитание. Мы говорим об " усеченном вычитании"   при   и   при  , поскольку мы имеем дело только с натуральными (целыми неотрицательными) числами. Одноместная функция усеченного вычитания единицы определяется рекурсивно:

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

29.Неограниченный оператор минимизации. Примеры. Определение частично-рекурсивной функции.

Оператор минимизации аргумента. Пусть f — функция от n  натуральных переменных. Тогда результатом применения оператора минимума аргумента к функции f называется функция h от n − 1 переменной, задаваемая следующим определением:     , при условии 

 То есть функция h возвращает минимальное значение последнего аргумента функции f, при котором её значение равно 0.

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

Минимизация. Скажем, что функция Fⁿ(x₁,... ,x_n) получена с помощью оператора минимизации(   -оператора) из функцииgⁿ⁺¹(x₁,..., x_n,y), если Fⁿ(x₁,...,x_n) определена и равна y тогда и только тогда, когда все значения gⁿ⁺¹(x₁,..., x_n,0),...,gⁿ⁺¹(x₁,..., x_n,y-1) определены и не равны 0, а gⁿ⁺¹(x₁,..., x_n,y)=0. В этом случае будем писать

Частично рекурсивные функции. Функция f называется частично рекурсивной функцией (ч.р.ф.), если она является одной из простейших функций или может получиться из них с помощью конечного числа применений операторов суперпозиции, примитивной рекурсии иминимизации, т.е. существует последовательность функций f₁,f₂,..., f_n=f, каждая из которых является либо простейшей, либо получена из предыдуших с помощью одного из указанных операторов. Указанная последовательность функций называется частично рекурсивным описанием функции f.

Функция f называется общерекурсивной функцией (о.р.ф.), если она частично рекурсивна и всюду определена.

Функция f называется примитивно рекурсивной функцией (п.р.ф.), если она частично рекурсивна и для нее существует частично рекурсивное описание, использующее лишь операторы суперпозиции и примитивной рекурсии. В таком случае оно называется примитивно рекурсивным описанием функции f.

Нетрудно проверить, что каждая примитивно рекурсивная функция всюду определена, т.е. является общерекурсивной (обратное, вообще говоря, неверно).