Пусть дана функция и функция .
Определение
Говорят, что функция получена из функций и с помощью операции примитивной рекурсии, если выполняются следующие равенства:
,
.
Это определение имеет смысл, когда , при этом записывается
=
или сокращенно
,
где - операция примитивной рекурсии.
В случае, когда , то операция примитивной рекурсии примет вид:
,
,
и обозначается:
.
Пример 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(x1x2)=m(y–x1=x2);
Целесообразность применения рекурсии в программировании обусловлена спецификой задач, в постановке которых явно или опосредовано указывается на возможность сведения задачи к подзадачам, аналогичным самой задаче. При этом эффективность рекурсивного или итерационного способов решения одной и той же задачи определяется в ходе анализа работоспособности программы на различных наборах данных. Таким образом, рекурсия не является универсальным способом в программировании. Ее следует рассматривать как альтернативный вариант при разработке алгоритмов решения задач.
Контрольные вопросы:
1. Какие функции называются элементарными? Перечислите их.
2. В чем состоит операция подстановки?
3. В чем состоит операция примитивной рекурсии?
4. Что называется оператором? Какие операторы существуют?
5. Какая функция называется примитивно-рекурсивной?