Історично першою алгоритмічною системою була система, заснована на використанні конструктивно визначених арифметичних (цілочисельних) функцій, які назвали рекурсивними. Значення такої функції Y для будь-якого довільного значення аргумента х (з області визначення функції) знаходиться через значення цієї функції від аргумента х – 1. Тобто можна побудувати рекурентні співвідношення, які визначають, як саме залежить f(x) від f(x – 1).
Застосування рекурсивних функцій у теорії алгоритмів засновано на ідеї нумерації слів у довільному алфавіті послідовними натуральними числами.
Наприклад, таку нумерацію можна здійснити, розміщуючи слова у порядку зростання їх довжини, а слова, що мають однакову довжину, — у довільному лексикографічному порядку.
Після нумерації вхідних та вихідних слів будь-який алфавітний оператор перетворюється на функцію y = f(x), де х та у приймають цілі невід’ємні значення. Причому функція f(x) може бути визначена тільки для тих х, що належать області визначення цієї функції.
Подібні частково визначені цілочисельні функції називають арифметичними. При побудові алгоритмів використовується деякий набір елементарних арифметичних функцій, таких як:
1) функції, тотожньо рівні 0: f(x) = 0; для всіх х;
2) функції, тотожньо рівні аргументу: f(x) = x;
3) функції безпосереднього слідування: f(x) = x + 1.
Із цих елементарних арифметичних функцій за допомогою невеликої кількості операцій будують більш складні функції, що не виходять за межі класу рекурсних функцій. До них належать такі операції: суперпозиції, примітивної рекурсії, найменшого кореня.
Операція суперпозиції полягає у підстановці одних арифметичних функцій замість аргументів інших функцій.
Наприклад, нехай є
f(x) = 0;
g(x) = x + 1;
h(x) = g(f(x)).
Тоді:
h(0) = g(0) = 0 + 1 = 1;
h(x) = g(0) = 0 + 1 = 1.
Тобто отримали функцію, яка тотожньо дорівнює 1.
Якщо h(x) = g(g(x)), то h(x) = g(x + 1) = x + 1 + 1 = 2 і т.д.
Операція примітивної рекурсії дозволяє побудувати функцію, залежну від n + 1 аргумента, якщо відомі дві функції — одна від n аргументів, друга — від n + 2 аргументів.
Наприклад, побудуємо двомісну функцію додавання f(x, y) = x + y, якщо є одномісна g(x) = x; та тримісна h(x, y, z) = z +1. (Кількість аргументів можна збільшувати як завгодно.)
Завдяки операції примітивної рекурсії здійснимо побудову функції. Нехай
f(x, 0) = g(x);
f(x, y + 1) = h(x, y, f(x, y)); f(x, 0) = g(x) = x;
f(x, 1) = h(x, 0, f(x, 0)) = h(x, 0, x) = x + 1;
f(x, 2) = h(x, 1, f(x, 1)) = h(x, 1, x + 1) = x + 2;
. . .
f(x, y – 1) = h(x, y – 2, f(x, y – 2)) = h(x, y – 2, x + y – 2) = x + y – 1;
f(x, y) = h(x, y – 1, f(x, y – 1)) = h(x, y – 1, x + y – 1) = x + y.
Таким чином побудовано функцію, залежну від двох аргументів, значення якої обчислюються для будь-якого значення х, коли у змінюється від 0 до будь-якого цілого.
Функції, які можна побудувати з елементарних арифметичних функцій за допомогою операцій суперпозиції та примітивної рекурсії, називають примітивно рекурсивними.
Операція найменшого кореня, або операція мінімізації, дозволяє побудувати функцію f від n аргументів, якщо відома функція g, залежна від n + 1 аргумента, тобто зменшити кількість аргументів функції.
Нехай маємо функцію від n + 1 аргумента g(x1, x2 ... xn, y).
Побудуємо функцію від n аргументів f(x1, x2 ... xn).
Задамо значення для n аргументів функції g:
x1 = a1 ; x2 = a2 ... xn = an.
Підставимо ці значення у формулу, що визначає функцію g, отримаємо: g(а1, а2 ... аn, у).
Дорівняємо цей вираз до нуля і розв’яжемо рівняння відносно у:
g(a1, a2 ... an, y) = 0.
Нехай отримали y = a.
Вважатимемо це значення у за значення функції f від тих самих значень х1 ... хn :
f(a1 ... an) = a.
Діючи так, ми можемо визначити функцію f від будь-яких значень її аргументів. Отже, функцію f побудовано.
Наприклад:
g(x, y, z) = x + y +z f(x, y) = ?
g(0, 0, z) = 0 + 0 + z = 0 z = 0 f(0, 0) = 0
g(1, 0, z) = 1 + 0 + z = 0 z = –1 f(1, 0) = –1
g(0, 1, z) = 0 + 1 + z = 0 z = –1 f(0, 1) = –1
. . .
g(5, 2, z) = 5 + 2 + z = 0 z = -7 f(5, 2) = –7
g(–6, 1, z) = –6 + 1 + z = 0 z = 5 f(–6, 1) = 5
f(x, y) = –x – y
