Рекурсивные функции.

Рекурсивная функция (частично рекурсивная функция) – функция, заданная с помощью последовательности частичных (определенных не обязательно для всех значений своих аргументов) функций таких, что каждая функция последовательности либо является (базисной) простейшей функцией, либо получена из предыдущих с помощью операторов суперпозиции (подстановки) Sⁿ_m, примитивной рекурсии R_n и минимизации .

Все рекурсивные функции являются вычислимыми функциями, то есть для любой такой функции можно указать алгоритм вычисления ее значений. Очевидно, что всякий алгоритм однозначно ставит в соответствие исходным данным (в случае, если он определен на них) результат. Поэтому с каждым алгоритмом однозначно связана функция, которую он вычисляет. Однако, обратное, то есть: «для всякой функции существует вычисляющий ее алгоритм», неверно.

Согласно тезису Черча, любая функция, считающаяся вычислимой в интуитивном смысле, является рекурсивной функцией. Эта гипотеза (тезис) подтверждается тем, что все известные вычислимые функции являются рекурсивными. Тезис Черча позволяет придать интуитивному понятию вычислимой функции точный алгоритмический смысл.

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

В теории рекурсивных функций, рассматриваемой ниже, как и вообще в теории алгоритмов, принят конструктивный, финитный подход, основной чертой которого является то, что все множество исследуемых объектов (в данном случае функций) строится из конечного числа исходных объектов – базиса – с помощью простых операторов (операций), эффективная выполнимость которых достаточно очевидна.

Замечание:

Всюду определенные рекурсивные функции называются общерекурсивными функциями.