Рекурсивная функция

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

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

Если значения функции найдены не для всех значений области определения, то её называют частично рекурсивной функцией и, наоборот, если они найдены для всех значений области определения, то её называют общерекурсивной функцией.

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

Базовые функции

Функция константа. Если дано f = (x₁, x₂,..., x_n, у| x_i, yÎN[1]) = C_n, то любым значениям независимых переменных из множества {x_i} (iÎ{1,2,…,n}) аргумента функции ставится в соответствие значение функции у, равное постоянной величине (константе) - С_n, где n –число независимых переменных аргумента. Поскольку чаще всего C_n=0, то функцию константы называют также нуль-функцией.

Пример1: дано: f = (x₁, x₂, x₃, у) = C₃. Тогда:

· для x₁=5, x₂=4, x₃=7 и C₃=0 имеем у = C₃(5, 4, 7) = 0;

· для x₁=5, x₂=4, x₃=7 и С₃=1 имеем y = C₃(5, 4, 7) = 1.

Пример2: дано: f = (x₁, x₂, у) = C₂. Тогда для x₁=15, x₂=3 и С₂=41 имеем y = С₂(15, 3) = 41.

Как видно из примеров, значение функции константы не зависит от значений аргументов x_i, а определяется только значением самой константы С_n.

Функция тождества. Если дано f = (x₁, x₂,...,, x_n, у| x_i, y∈N) = I_n^m, то любым значениям независимых переменных из множества {x_i} (iÎ{1,2,…,n}) аргумента функции ставится в соответствие значение y функции, равное значению m-го независимого переменного аргумента, где 1 £ m £ n – место независимого переменного аргумента в упорядоченном списке аргументов. Поэтому данную функцию называют также функцией выбора аргумента.

Пример1: дано f = (x₁, x₂, x₃, у) = I₃². Тогда для x₁=5, x₂=4, x₃=7 имеем у = I₃²(5, 4, 7) = 4.

Пример2: дано f = (x₁, x₂, x₃, у) = I₃³. Тогда для x₁=5, x₂=4, x₃=7 имеем у = I₃³(5, 4, 7) = 7.

Функция следования. Если дано f = (x, у| x, y∈N) = l(x), то любому значению независимой переменной из множества {x_i} (iÎ{1,2,…,n}) аргумента функции ставится в соответствие значение функции y, равное числу, непосредственно следующему за числом, являющимся значением независимой переменной.

Пример1: дано f = (x, у) = l(x). Тогда для x=5 имеем у = l(5) = 6, поскольку 6 = 5+1.

Пример2: дано f = (x, у) = l(x). Тогда для x=7 имеем у = l(7) = 8, поскольку 8 = 7+1.