Рекурсія — це метод опису, визначення або розв’язання задачі, при якому об’єкт визначається через самоподібний до себе об’єкт. У математиці та інформатиці рекурсія є фундаментальним принципом, що дозволяє розбивати складні задачі на простіші підзадачі одного типу.
Загальне визначення
Рекурсія (від лат. recursio — «повернення») — це процес, у якому функція, процедура або визначення звертається до самої себе, прямо або опосередковано, для розв’язання задачі.
У формальному вигляді рекурсивний об’єкт складається з:
- базового випадку (умови зупинки)
- рекурсивного кроку (зведення задачі до меншої або простішої версії самої себе)
Рекурсія в математиці
У математиці рекурсія використовується для визначення функцій, послідовностей і структур.
Приклад — факторіал:
n! = n × (n − 1)!
0! = 1 (базовий випадок)
Інші приклади:
- числа Фібоначчі
- рекурсивні ряди
- фрактальні структури (наприклад, множина Мандельброта)
Рекурсія в інформатиці
У програмуванні рекурсія — це техніка, коли функція викликає саму себе.
Типова структура:
- перевірка базового випадку
- виклик самої себе з меншими вхідними даними
Приклад (псевдокод факторіала):
function factorial(n):
if n == 0:
return 1
return n * factorial(n – 1)
Види рекурсії
Пряма рекурсія
Функція викликає саму себе напряму.
Непряма рекурсія
Функція A викликає функцію B, яка в свою чергу викликає A.
Лінійна рекурсія
Кожен виклик породжує лише один новий виклик.
Деревоподібна рекурсія
Кожен виклик породжує кілька нових викликів (наприклад, Фібоначчі).
Хвостова рекурсія
Рекурсивний виклик є останньою операцією функції, що дозволяє оптимізацію.
Рекурсія в структурах даних
Рекурсія природно застосовується до:
- дерев (бінарні дерева, дерева пошуку)
- графів (обхід у глибину)
- списків (рекурсивне визначення елементів)
Наприклад, кожне дерево можна визначити як:
- порожнє дерево
- вузол, що містить піддерева
Рекурсія в алгоритмах
Рекурсивні алгоритми часто використовуються для:
- сортування (швидке сортування, merge sort)
- пошуку
- обходу структур даних
- розв’язання задач «поділяй і володарюй»
Переваги рекурсії
- природний спосіб опису складних задач
- компактний і зрозумілий код
- добре підходить для дерев і ієрархій
Недоліки рекурсії
- велика витрата пам’яті через стек викликів
- ризик переповнення стеку (stack overflow)
- іноді менш ефективна ніж ітерація
Рекурсія та ітерація
Рекурсію часто можна замінити циклом (ітерацією), але:
- рекурсія краще виражає структуру задачі
- ітерація зазвичай ефективніша за ресурсами
Рекурсія в природі та науці
Рекурсивні або самоподібні структури зустрічаються у:
- фракталах (сніжинка Коха, папороті)
- біології (розгалуження судин, дерев)
- фізиці (масштабна інваріантність)
Філософський аспект
Рекурсія також використовується як метафора:
- самопізнання (система, що аналізує себе)
- самоподібні структури мислення
- нескінченні визначення або парадокси
Типові проблеми рекурсії
- відсутність базового випадку → нескінченний цикл
- надмірна глибина викликів
- дублювання обчислень (вирішується мемоізацією або динамічним програмуванням)
Рекурсія є одним із ключових принципів сучасної математики та інформатики. Вона дозволяє описувати складні системи через їх простіші копії, роблячи її потужним інструментом для моделювання, алгоритмізації та аналізу структур будь-якої складності.