Рекурсія. Побіжний погляд

image
Нижче мова піде про старенькій рекурсії, яку непогано було б уявляти, розуміти і застосовувати.
Примітка: Ця невелика стаття написана для побіжного ознайомлення з рекурсією, деякими прикладами її застосування і небезпеками.
Визначення
Для початку варто сказати, що рекурсія відноситься не тільки до програмування. Рекурсія — це загальне поняття, яке може бути притаманне чого завгодно і зустрічатися у повсякденному житті, але найбільше вона поширена в інформатики та математики. Для програмістів ж уміння застосовувати рекурсію — великий плюс в колекцію корисних навичок.
Найбільша дурість — це робити те ж саме і сподіватися на інший результат.
Під рекурсією розуміють процес повторення елементів самоподібних чином. Об'єкт має рекурсією, якщо він є частиною самого себе.
Приватним випадком рекурсії є хвостова рекурсія. Якщо будь-рекурсивний виклик є останньою операцією перед поверненням з функції, то це воно.
Деякі приклади
Рекурсію треба б зрозуміти, а визначення для цього підходить гірше, ніж наочні приклади. Для кращого розуміння, звичайно, все ж слід прочитати визначення, подивитися на приклад, знову прочитати визначення і знову подивитися на приклад… Повторювати, доки не прийде усвідомлення.
Відмінний приклад ви можете знайти на тут.
найвідоміше програмісту застосування рекурсії — задачі на обчислення чисел Фібоначчі або факторіала. Давайте покажемо, як це реалізувати на мові C:
int fib(int n) { 
if (n == 0) return 0; 
if (n == 1 || n == 2) return 1; 
return fib(n - 1) + fib(n - 2); 
} 

Можна показати, як це виглядало б на Prolog
fib(1,1):-!.
fib(2,1):-!.
fib(N,R):- 
N1 is N-1, fib(N1, R1), 
N2 is N-2, fib(N 2, R2), 
R is R1 + R2.

Тут же варто відзначити, що декларативна парадигма, зокрема парадигма логічного програмування, набагато краще дозволяє зрозуміти рекурсію, так як там це звичайна справа.
Обчислення факторіала. Приклад хвостової рекурсії
int factorial_rec(int n, int res) {
if (n == 0) return res;
return factorial_rec(n - 1, res * n);
}
int factorial(int n) {
return factorial_rec(n, 1);
}

Ще один небезпечний і цікавий прикладFork-бомба
Примітка: Рекурсивне створення процесів вкрай швидко (через експоненціального зростання їх кількості) заповнює таблицю процесів, що досить небезпечно для системи.
#include <unistd.h>
int main() {
while(true) fork();
}

Reboot кнопкою після такого робити трохи не приємно.
Для математика першою асоціацією, швидше за все, буде фрактал. Фрактали прекрасні і приємно для ока показують властивості самоподібності.
найвідоміші фрактали:
Крива (сніжинка) Кохаimage
Трикутник Серпінськогоimage
Дерево Піфагораimage
Ну і в повсякденному житті класичним прикладом є два дзеркала, поставлені одне навпроти одного.
Зануритися глибше
image
Проста чи рекурсія? Однозначно ні. На вигляд здається, що все просто, однак рекурсія таїть в собі небезпеку (А іноді вона просто не зрозуміла).
Повернемося до прикладу з обчисленням чисел Фібоначчі. Відразу зауважимо, що її обчислене результатом функції є виклик цієї функції, а якщо бути точніше, то сума результатів виклику двох функцій (саме тому рекурсія не хвостова). Стає зрозуміло, що другий виклик не відбудеться, поки не завершиться перший (в якому також буде виклик двох функцій). Тут же допитливий розум помітить, що з рекурсивної функції повинен існувати "нормальний" вихід, без самовызова, інакше ми познайомимося з переповненням стека викликів — це один з ключових моментів, який варто тримати в голові при роботі з функціями викликають самі себе.
Зауважимо, що дерево викликів вийде великим, але максимальна кількість викликів в стеку буде помітно менше (N-1 при N > 2, відповідно).
Приклад дерева викликів для числа 6image
Рекурсивні алгоритми досить-таки часто зустрічаються при роботі з деревами, сортировками і завданнями на графах. Так що, щоб краще вникнути потрібна практика і для цього не погано підходить вищезгадане (зокрема, бінарні чи загальні дерева. Їх реалізація не так складна, а досвід роботи з рекурсією вийде не поганий).
Крім цього хотілося б згадати Ханойські вежі, які також відмінно підійдуть для ознайомлення з рекурсивними завданнями. На Хабре також був відмінний дослідження цієї гри.
Для повноти картини обов'язково треба згадати про боротьбу з рекурсією.
Навіщо з нею боротися?
Підвищується продуктивність. Але це не означає, що з нею просто необхідно боротися, адже застосування рекурсії очевидніше, простіше і приємніше, ніж ітераційні варіанти.
Під силу подолати будь-яку рекурсію?
Однозначно так. Будь рекурсивний алгоритм можна переписати без використання рекурсії, а хвостову рекурсію ж дуже легко перевести на ітерацію (чим і займаються деякі компілятори для оптимізації). Це також відноситься і до ітераційним алгоритмом.
найвідоміший спосіб — це використання стека. Тут докладніше, для цікавляться.
Висновок
Спасибі за прочитання статті. Сподіваюся, що більшість не знайомих з рекурсією отримали базове уявлення про неї, а від знаючих людей, звичайно, хочеться почути доповнення і зауваження в коментарях. Не бійтеся рекурсії і не переповнюйте стек!
UPD: Додано коректний приклад хвостової рекурсії.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.