Суперпозиція позначається як Sn+1, де n+1 - кількість функцій.
Прийом примітивної рекурсії дозволяє будувати функцію f від n+1
аргументу по двох вхідних функціях: функції g від n аргументів і функції h
від n+2 аргументів, якщо:
f (x1, x2, ... , xn, 0) = g (x1, x2, ... , xn);
f (x1, x2, ... , xn, y + 1) = h (x1, x2, ... , xn, y, f (x1, x2, ... , xn, y)).
Це означає, що значення f (x1, x2, ... , xn, m+1) можна розрахувати за
допомогою ітераційної рекурсивної процедури:
b0 = g (x1, x2, ... , xn)
b1 = h (x1, x2, ... , xn, 0, b0 )
b2 = h (x1, x2, ... , xn, 1, b1 )
...... ...... ...... ...... ...... ...... ...... ...... ....
bm+1= h (x1, x2, ... , xn, m, bm)
===========================
f (x1, x2, ... , xn, m+1) = bm+1
Прийом найменшого кореня дозволяє визначити нову арифметичну
функцію f (x1, x2, ... , xn) від n аргументів за допомогою раніше побудованої
арифметичної функції g (x1, x2, ... , xn, y) від n+1 аргументів.
Для будь-якого заданого набору значень змінних x1 = a1, ... , xn= an у
якості значення f (a1, a2, ... , an) обумовленої функції приймається
найменший цілий ненегативний корінь у = а рівняння g (x1, x2, ... , xn, y) =
0. У випадку неіснування цілих ненегативних коренів цього рівняння функція
f(x1, x2, ... , xn) вважається невизначеною на відповіднім наборі значень
змінних.
Арифметичні функції, що можуть бути побудовані з елементарних
арифметичних функцій за допомогою конструктивних прийомів суперпозиції,
примітивної рекурсії і найменшого кореня, називають частково
рекурсивними функціями. Якщо такі функції до того ж усюди визначено, то
вони називаються загальнорекурсивними функціями.
Практично поняття частково рекурсивних функцій використовується
для доказу алгоритмічної можливості (або неможливості) розв'язання задач.
Використання ж таких функцій для утворення конкретного алгоритму є
практично недоцільним через складність процесу алгоритмізації.