При построении рекурсивных функций принят традиционный в теории алгоритмов конструктивный подход: задается « базис », т.е. несколько простейших, очевидным образом вычислимых функций и способ построения из них остальных функций с помощью специальных операторов.
В качестве простейших функций в теории рекурсивных функций приняты следующие :
1.– константа «ноль».
2.– « последователь »
3.– функция тождества или выбора аргумента.
Эти функции можно считать простейшими, т.к. для любых значений аргументов из натурального ряда мы немедленно определяем значение функции.
Для построения примитивно-рекурсивных функций используются операторы суперпозиции и примитивной рекурсии.
Оператором суперпозиции называется подстановка в функцию от m переменных m функций от n переменных, что дает новую функцию от n переменных. Суперпозицией функций g и называют функцию