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

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

Определение

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

,

.

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

=

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

,

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

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

,

,

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

.

Пример 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. Какая функция называется примитивно-рекурсивной?