Лекция: Оператор примитивной рекурсии (с41)

Оператор примитивной рекурсии задается следующим образом:

Рекурсия ведется по одному аргументу, все остальные считаются параметрами.

В нуле функция равна функции g, а в некоторой точке y+1 она определяется через известную функцию h и значение этой же функции в предыдущей точке.

Приведенная пара равенств называется схемой примитивной рекурсии.

Принципиальная разница между рекурсией и суперпозицией в том, что для вычисления значения в точке y+1 нужно вычислить значение во всех предыдущих точка.