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

В качестве простейших функций в теории рекурсивных функций приняты следующие :

1.– константа «ноль».

2.– « последователь »

3.– функция тождества или выбора аргумента.

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

Для построения примитивно-рекурсивных функций используются операторы суперпозиции и примитивной рекурсии.

Оператором суперпозиции называется подстановка в функцию от m переменных m функций от n переменных, что дает новую функцию от n переменных. Суперпозицией функций g и называют функцию