Рекурсія - один з основних прийомів програмування. Рекурсивні функції - функції, що залежать самі від себе. Коли ми розглядали автомати, то говорили про функції переходів, які в наступний момент автоматного часу залежать від своїх значень в попередній момент часу. Так реалізується автоматна пам'ять. В теорії рекурсивних функцій, яка вважається історично першої формалізацією поняття алгоритму, застосовується нумерація слів в довільному алфавіті натуральними числами (N), і будь-який алгоритм зводиться до обчислення деякої функції при цілочисельних значеннях аргументів [22].
Функція обчислюваності, якщо існує такий алгоритм, тобто покрокова процедура «від простого до складного», яка за вхідним набору змінних обчислює значення функції, якщо цей вхідний набір належить до області визначення функції, або видає повідомлення, що вхідний набір не належить до області визначення функції.
Функція полувичісліма, якщо при завданні вхідного набору, що не належить області визначення функції, алгоритм не закінчується роботу ( «зациклюється»). Теорію обчислюваності розробляв А. Черч. Ідея була схожа на вивчену нами проблему функціональної повноти переключательних функцій: виділити елементарні обчислюваної функції (які «інтуїтивно обчислюваних») - тобто базис і запропонувати засоби отримання з цих елементарних обчислюваних функцій більш складних функцій за кінцеве число кроків (як принцип суперпозиції в теорії перемикальних функцій). Отримані таким чином функції теж будуть обчислюваності.
Такими елементарними обчислюваної функції є:
1) S (x) = x + 1, (N N), функція проходження (зазначає таке натуральне число);
2) 0 (х) = 0, константа нуля;
3) Im (x1 x2 ... xn) = xm - проектує функція, результатом якої є вибір m-го з n аргументів.
Для отримання з одних полувичіслімих функцій інших функцій за кінцеве число кроків були запропоновані так звані оператори.
Першим з них є відомий нам оператор суперпозиції, тобто підстановка в функціюфункцій замість змінних. При цьому збільшується розмірність функції.
Другим оператором є оператор примітивної рекурсії.
Розглянемо приклад завдання числового ряду Фібоначчі 1,1,2,3,5,8,13,21, ... з використанням оператора примітивної рекурсії:
Тут вказуються два початкових значення функції f (0), f (1) і принцип формування подальшого значення. На відміну від функцій переходів автомата, вказується не автоматне час, а крок обчислень n, тобто значення функції на певному етапі, відмінному від нульового і першого, дорівнює сумі значень функції на двох попередніх етапах.
Розглянемо ще один приклад використання оператора примітивної рекурсії:
f (0) = 1, f (1) = f (0) × 1 = 1, f (2) = f (1) × 2 = 2, f (3) = f (2) × 3 = 6, ...
Таким чином, ми задали функцію факторіала: x!
Функції, одержувані з елементарних, шляхом кінцевого числа застосувань операторів суперпозиції і примітивної рекурсії, називаються примітивно-рекурсивними. Розглядається і більш складна рекурсія, наприклад, кратна, по кільком змінним одночасно [19].
Чи всі функції є примітивно - рекурсивними? Можна показати, що безліч всіх одномісних цілочисельних функцій типу N N, де N - безліч натуральних чисел, незліченні, тим більше це вірно для функції типу N n N. Кожна примітивно-рекурсивна функція має кінцеве опис, тобто задається кінцевим словом у деякому фіксованому для всіх функцій алфавіті [19]. Безліч всіх кінцевих слів лічильно, тому примітивно-рекурсивні функції утворюють не більше ніж рахункове підмножина незліченну безлічі функцій типу N n N. Більш того, виявляється, не всі обчислюваної функції можна описати як примітивно-рекурсивні.
Третім оператором є оператор мінімізації m. який дозволяє вводити в обчислення перебір для визначення потрібного значення.
Нагадаємо, що x1. x2 є натуральними числами. Такі функції називаються частково рекурсивними, тобто вони не повністю визначені, на відміну від повністю певних примітивно-рекурсивних. У відповідність з тезою Черча функція полувичісліма, якщо і тільки якщо вона частково рекурсивна.
Є невичіслімие функції, в яких зв'язок між вхідними і вихідними величинами настільки складна, що неможливо поставити строго певний покроковий процес перетворення вихідних даних в результат [36], тобто не можна побудувати алгоритм рішення відповідної задачі.
Рекурсивні функції - основа функціонального програмування. Прикладом мови функціонального програмування є мова LISP, розроблений в 1960 р Д Маккарті. Це один з перших мов обробки даних в символьній формі (LISP, від LISt Processing - обробка списків). Одним з найбільш істотних властивостей мови LISP є те, що дані, програми і навіть сама мова - є просто списки символів в дужках. Подібна структура дозволяє писати програми або підпрограми, здатні звертатися самі до себе [37].
У LISP використовується префиксная форма запису:
Визначення функцій та їх обчислення в мові засновано на так званому лямбда-численні, введеному в 1931 р А Черчем:
де # 955; - визначення функції, х1, ..., хn - формальні параметри (лямбда список), fn - тіло функції.
Рекурсії присутні і в мовах структурного програмування.
Розглянемо приклад вирішення задачі на Паскалі, який використовує рекурсію [3].
З а д а ч а. Відомо рекурсивне визначення факторіала:
Тут n - невід'ємне. Записати цю функцію на мові Паскаль.
Рішення. У першому рядку визначення явно зазначено, як обчислити факторіал, якщо аргумент дорівнює нулю або одиниці. У будь-якому іншому випадку для обчислення n! необхідно обчислити попереднє значення (n-1)! і помножити його на n. Зменшується значення гарантує, що в кінці кінців виникне необхідність знайти 1! або 0. які обчислюються безпосередньо.
begin if (i = 1) or (i = 0)
begin write ( 'Введіть потрібне значення n');
writeln ( 'Факторіал', n, 'дорівнює', fact (n));
Зауважимо, що на час виконання допоміжного алгоритму основної алгоритм призупиняється. При виклику нової копії рекурсивного алгоритму знову виділяється місце для всіх змінних, які декларуються в ньому, причому змінні інших копій будуть недоступні. При видаленні копії рекурсивного алгоритму з пам'яті видаляються і всі його змінні. Активізується попередня копія рекурсивного алгоритму, стають доступними її змінні. Нехай необхідно обчислити 4. Основний алгоритм: вводиться n = 4, виклик fact (4). Основний алгоритм призупиняється, викликається і працює fact (4): 4<>1 і 4<>0, тому fact: = fact (3) * 4. Робота функції припиняється, викликається і працює fact (3): 3<>1 і 3<>0, тому fact: = fact (2) * 3. В даний момент в пам'яті комп'ютера дві копії функції fact. Викликається і працює fact (2): 2<>1 і 2<>0, тому fact: = fact (1) * 2. У пам'яті комп'ютера вже три копії функції fact і викликається четверта. Викликається і працює fact (1): 1 = 1, тому fact (1) = 1. Ця функція завершена, продовжує роботу fact (2). fact (2): = fact (1) * 2 = 1 * 2 = 2. Ця функція також завершена, і продовжує роботу функція fact (3). fact (3): = fact (2) * 3 = 2 * 3 = 6. Завершується робота і цієї функції, і продовжує роботу функція fact (4). fact (4): = fact (3) * 4 = 6 * 4 = 24. Після чого управління передається в основну програму і друкується відповідь: «Факторіал 4 дорівнює 24».