Примитивно рекурсивные функции (ПРФ)

⇐ ПредыдущаяСтр 2 из 2

Примитивно рекурсивные функции (ПРФ)

Определение

Элементарными функциями называются:

1) функция константы , где ,

2) функция следования

3) функция выбора , где .

Операция подстановки

Пусть задана функция и функции , , …, .

Определение

Говорят, что функция получена из этих функций с применением операции подстановки, если выполняется следующее равенство:

и обозначается:

где - операция подстановки.

Операция примитивной рекурсии

Пусть дана функция и функция .

Определение

Говорят, что функция получена из функций и с помощью операции примитивной рекурсии, если выполняются следующие равенства:

Это определение имеет смысл, когда , при этом записывается

или сокращенно

где - операция примитивной рекурсии.

В случае, когда , то операция примитивной рекурсии примет вид:

и обозначается:

Пример 1

Пусть , и покажем, что = , где .

Согласно определению операции примитивной рекурсии

Тогда,

…

Предположим, что для некоторого последнее равенство справедливо и докажем, что тогда

Действительно, пусть для некоторого . Тогда по определению операции примитивной рекурсии получаем, что

Таким образом, функция получается из функций и с помощью операции примитивной рекурсии.

Пример 2

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

Для решения задачи нахождения элементарных функций воспользуемся определением операции примитивной рекурсии, после чего получим, что

Тогда,

…

Очевидно, что функция - есть результат операции примитивной рекурсии над функциями и .

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

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

Вторым оператором является оператор примитивной рекурсии.

Рассмотрим пример задания числового ряда Фибоначчи 1,1,2,3,5,8,13,21,… с использованием оператора примитивной рекурсии:

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

Тогда f(0)=1, f(1)=1, f(2)=f(0)+f(1)=1+1=2, f(3)=f(1)+f(2)=1+2=3, f(4)=f(2)+f(3)=2+3=5,…

Рассмотрим другой пример использования оператора примитивной рекурсии:

f(0)=1, f(1)=f(0)×1=1, f(2)=f(1)×2=2, f(3)=f(2)×3=6, …

Таким образом, мы задали функцию факториала: x!

Функции, получаемые из элементарных, путем конечного числа применений операторов суперпозиции и примитивной рекурсии, называются примитивно-рекурсивными. Рассматривается и более сложная рекурсия, например, кратная, по нескольким переменным одновременно.

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

Например:

f(x₁x₂)=m(y–x₁=x₂);

Целесообразность применения рекурсии в программировании обусловлена спецификой задач, в постановке которых явно или опосредовано указывается на возможность сведения задачи к подзадачам, аналогичным самой задаче. При этом эффективность рекурсивного или итерационного способов решения одной и той же задачи определяется в ходе анализа работоспособности программы на различных наборах данных. Таким образом, рекурсия не является универсальным способом в программировании. Ее следует рассматривать как альтернативный вариант при разработке алгоритмов решения задач.

Контрольные вопросы:

1. Какие функции называются элементарными? Перечислите их.

2. В чем состоит операция подстановки?

3. В чем состоит операция примитивной рекурсии?

4. Что называется оператором? Какие операторы существуют?

5. Какая функция называется примитивно-рекурсивной?

⇐ Предыдущая 12