Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 7 стр.

                                       2. РЕКУРСИВНЫЕ ФУНКЦИИ


        2.1. Общие сведения
    Первой алгоритмической системой была система, основанная на использовании
конструктивно определяемых арифметических (целочисленных) функций, получивших
специальное название рекурсивных функций.
    Рекурсией называется способ задания функции, при котором значение определяемой
функции для произвольных значений аргументов выражается известным образом через
значения определяемой функции для меньших значений аргументов.
    Применение рекурсивных функций в теории алгоритмов основано на идее нумерации
слов в произвольном алфавите последовательными натуральными числами. Наиболее просто
такую нумерацию можно осуществить, располагая слова в порядке возрастания их длин, а
слова, имеющие одинаковую длину, - в произвольном порядке.
    После нумерации входных и выходных слов в произвольном алфавитном операторе этот
оператор превращается в функцию y = f(x), в которой аргумент х и функция y принимают
неотрицательные целочисленные значения. Функция f(x) может быть определена не для всех
значений х, а лишь для тех, которые составляют область определения этой функции.

        2.2. Понятие простейших функций
    Числовые функции, значение которых можно установить посредством некоторого
алгоритма, называются вычислимыми функциями.
    Для того чтобы описать класс функций с помощью рекурсивных определений,
рассмотрим набор простейших функций:
    1) Z(x1, x2, ..., xn) = 0           - нуль-функция, которая определена для всех неотрицательных
значений аргумента;
    2) s(x) = x+1 - функция непосредственного следования, также определенная для всех
целых неотрицательных значений своего аргумента;
    3) I nm (x1, x2, . . ., xm, . . . , xn) = xm - функция выбора (тождества), повторяющая значения
своих аргументов.
    Используя простейшие функции в качестве исходных функций, можно с помощью
небольшого числа общих конструктивных приемов строить сложные арифметические
функции. В теории рекурсивных функций особо важное значение имеют три операции:
суперпозиции, примитивной рекурсии и минимизации.

        2.2.1. Оператор суперпозиции
    Оператором суперпозиции S называется подстановка в функцию от m переменных m
функций от n одних и тех же переменных. Она дает новую функцию от n переменных.
Например, из функций f(x1, x2, ..., xm), f1(x1, x2, ..., xn), f2(x1, x2, ..., xn), . . ., fm(x1, x2, ..., xn)
можно получить новую функцию:
Sm+1(f, f1, f2, ..., fm) = g(x1, x2, ..., xn) = f(f1(x1, x2, ..., xn), f2(x1, x2, ..., xn), ..., fm(x1, ..., xn)).
(1)
    В операции суперпозиции Sm+1 индекс сверху указывает на число функций.
    Таким образом, при помощи оператора суперпозиции и функции выбора можно
выразить любую подстановку функции в функцию.
    Например, осуществляя операцию суперпозиции функций f(x) = 0 и g(x) = x+1, получим
функцию:
    h(x) = g(f(x)) = 0 + 1 = 1.