На практиці мови програмування не є чисто процедурними, функціональними чи логічними, а містять в собі риси мов різних типів. На процедурній мові часто можна написати функціональну програму або її частину і навпаки. Може точніше було б замість типу мови говорити про стиль або методі програмування. Природно різні мови підтримують різні стилі в різному ступені.
Процедурне і функціональне програмування
Процедурна програма складається з операторів і пропозицій, які керують їх виконання. Типовими операторами є оператори присвоювання і передачі управління, оператори введення-виведення і спеціальні пропозиції для організації циклів. З них можна складати фрагменти програм і підпрограми. В основі такого програмування лежать взяття значення якоїсь змінної, вчинення над ним дії і збереження нового значення за допомогою оператора присвоювання, і так до тих пір поки не буде отримано (і, можливо, надруковано) бажане остаточне значення.
Функціональна програма складається з сукупності визначень функцій. Функції, в свою чергу, є виклики інших функцій і пропозицій, які керують викликами. Обчислення починаються з виклику деякої функції, яка в свою чергу викликає функції, що входять в її визначення і т.д. відповідно до ієрархією визначень і структурою умовних пропозицій. Функції часто або прямо, або опосередковано викликають самі себе.
Кожен виклик повертає деяке значення в викликала його функцію, обчислення якої після цього триває; цей процес повторюється до тих пір поки запустивши обчислення функція не поверне кінцевий результат користувачеві.
"Чисте" функціональне програмування не визнає присвоювання і передач управління. Розгалуження обчислень засноване на механізмі обробки аргументів умовного пропозиції. Повторні обчислення здійснюються через рекурсію, яка є основним засобом функціонального програмування.
Рекурсивний - значить використовує самого себе
Багато практичні ситуації припускають рекурсивне або самоповторяющееся поведінку, повертається до самого себе. Припустимо, що ми, наприклад, намагаємося прочитати текст на іншій мові, користуючись тлумачним словником цієї мови. Коли в тексті зустрічається незнайоме слово, то його пояснення шукається в словнику. У поясненні слова можуть, в свою чергу, зустрінеться незнайомі слова, які потрібно знайти в словнику і т.д. Цю процедуру можна визначити за допомогою наступних правил:
Рекурсія містить термінальну гілка
У рекурсивном описі дій має сенс звернути увагу на наступні обставини. По-перше, процедура містить як правило термінальні гілки і умова закінчення. По-друге, коли процедура доходить до рекурсивної гілки, то що функціонує процес припиняється і новий такий же процес запускається з початку, але вже на новому рівні. Перерваний процес яким-небудь чином запам'ятовується. Він буде чекати і почне виконуватися лише після закінчення нового процесу. У свою чергу, новий процес може призупинитися, очікувати і т.д.
Так утворюється як би дерево перерваних процесів, з яких виконується лише останні в даний момент часу процеси (листочки); після закінчення їх роботи залишиться активним передував їм процес. Цілком весь процес виконаний, коли дерево знову спорожніє, або, іншими словами, все перервані процеси виконуватися.
Рекурсія може проявлятися у багатьох формах
У реальному світі рекурсія проявляється у вигляді різних форм і зв'язків. Вона може бути як в структурі, так і в діях.
Кожному відомо зображення, що повторюється в двох дзеркалах, встановлених один проти одного, картина, яка зображує картину, телевізор, в якому видно телевізор, і т.д. В математиці рекурсія зустрічається в зв'язку з багатьма різними аспектами, такими як ряди, що повторюються лінії, алгоритми, процедури визначення та докази, одним словом, в самих різних структурах.
Рекурсія зустрічається зазвичай і в природі: дерева мають рекурсивне будова (гілки утворюються з інших гілок), річки утворюються з впадають в них річок. Клітини діляться рекурсивно. У рослинах це часто видно вже на макрорівні. Наприклад, насіннєва луска шишок і насіння деяких квітів (наприклад, соняшнику) часто розташовані пересічними спіралевіднимі віялами, що визначаються співвідношенням чисел Фібоначчі.
Продовження життя пов'язане з рекурсивним процесом. Молекули ДНК і віруси розмножуються, копіюючи себе, живі істоти мають потомство, яке, в свою чергу, теж має потомство і т.д.
Рекурсія поширена і в мові, і в поведінці так само, як в способах міркування і пізнання. Рекурсія в мові, наприклад, може бути в структурі або в утриманні:
"Петя сказав, що Вася сказав, що ..."
"Знаю, що знаю, але не пам'ятаю"
"Зробити; змусити зробити; змусити, щоб змусили зробити; ..."
"Заміни x цією пропозицією"
"Запам'ятай і передай це повідомлення"
...
Музичні форми і дії також можуть бути рекурсивними у багатьох відношеннях (наприклад, канон, в якому мелодія супроводжується тією ж мелодією з затримкою, і інші).
Цілеспрямоване поведінка і рішення проблем є рекурсивними процесами. Точно так само і дослідження в області штучного інтелекту рекурсивний в своїй спробі досліджувати процеси, що протікають в головному мозку, за допомогою яких відбувається дослідження і рішення проблем, в тому числі і дослідження в області штучного інтелекту.
Списки будуються рекурсивно
Рекурсія в Ліспі заснована на математичної теорії рекурсивних функцій. Рекурсія добре підходить для роботи зі списками, так як самі списки можуть складатися з подсписков, тобто мати рекурсивне будова. Для обробки рекурсивних структур цілком природно використання рекурсивних процедур.
Списки можна визначити за допомогою наступних правил Бекуса-Наура:
Лисп заснований на рекурсивном підході
У програмуванні на Ліспі рекурсія використовується для організації повторюваних обчислень. На ній же засновано розбиття проблеми і поділ її на підзадачі, вирішення яких, наскільки це можливо, намагаються звести до вже вирішеним або в Відповідно до основної ідеї рекурсії до розв'язуваної зараз задачі.
На рекурсії заснований і часто використовуваний при вирішенні завдань і при пошуку механізм повернень, за допомогою якого можна повернутися з тупикової гілки до місця розгалуження, анулювавши пророблені обчислення. Рекурсія в Ліспі є не тільки організацію обчислень - це образ думок і методологія вирішення завдань.
Теорія рекурсивних функцій
Теорія рекурсивних функцій поряд з алгеброю списків і лямбда-обчисленням є ще однією опорою, на якій покоїться Лисп. У цій області математики вивчаються теоретичні питання, пов'язані з обчислюваних. Під обчислюваності розуміються такі завдання, які в принципі можна запрограмувати і вирішити за допомогою обчислювальної машини. Теорія рекурсивних функцій пропонує поряд з машиною Тьюринга, лямбда-обчисленням і іншими теоретичними формалізмами еквівалентний їм формалізм алгоритмічної обчислюваності.
В теорії рекурсивних функцій самі функції (алгоритми) і їх властивості розглядаються і класифікуються відповідно до того, які функції можна отримати і обчислити, використовуючи різні форми рекурсії. Основна ідея рекурсивного визначення полягає в тому, що функцію можна за допомогою рекурентних формул звести до деяких початкових значень, до раніше певних функцій чи до самої обумовленою функції, але з більш "простими" аргументами. Обчислення такої функції закінчується в той момент, коли воно зводиться до відомим початковим значенням. Наприклад, числа Фібоначчі
0, 1, 1, 2, 3, 5, ...
використовуючи інфіксне нотацію Лиспа, можна визначити за допомогою наступних рекурентних формул:
(0 fib) = 0
(1 fib) = 1
(N fib) = (((n - 1) fib) + ((n - 2) fib))
Клас функцій, одержуваних таким чином, називають класом примітивно рекурсивних функцій.
Існують також функції, які не є примітивно рекурсивними. Як приклад можна привести функцію Аккермана, яку можна задати наступними рекурентними формулами:
(0 Ack x y) = (y + x)
(1 Ack x y) = (y * x)
(2 Ack x y) = (y ^ x)
... ((z + 1) Ack x y) = до значень y x-1 раз застосовується операція (lambda (u v) (z Ack u v))
Задана за допомогою наведеної вище схеми функція Ack не є примітивно рекурсивної, хоча вона і обчислювана, тобто її можна визначити і на основі цього визначення обчислити її значення за кінцевий час.
Можна показати, що існують функції, значення яких можна обчислити за допомогою алгоритму, але які не можна алгоритмічно описати. Обчислення такої функції може бути нескінченним. Як приклад наведемо функцію (n f m). результатом якої є 1 в разі, якщо в десяткового запису числа π зустрічається фрагмент з повторюваних цифр m довжиною n.
Можна показати, що алгоритм обчислення цієї функції існує, але нам невідомо, яка вона є. Ми можемо лише намагатися обчислювати знаки π в надії, що шуканий фрагмент виявиться, але визначити, чи закінчиться колись обчислення, ми не можемо. Такі функції називаються общерекурсівнимі.
Клас примітивно рекурсивних функцій досить цікавий з точки зору багатьох практичних проблем. Застосування рекурсивних функцій в Ліспі не обмежується лише чисельними аргументами, вони використовуються (і навіть в першу чергу) для символьних структур, що відкриває нові великі можливості в порівнянні з чисельними обчисленнями.