Рекурсивні функції

2.21. Рекурсивні функції

Рекурсія — це механізм, за якого функція викликає саму себе. На перший погляд це звучить як нескінченне зациклення, але в правильно написаній рекурсивній функції кожен наступний виклик отримує простіший варіант задачі, а вся послідовність завершується на конкретному базовому випадку. Рекурсія природно описує задачі, які мають вкладену самоподібну структуру: факторіал, числа Фібоначчі, обхід ієрархії файлів або структури даних типу дерево.

Два обов'язкових елементи рекурсивної функції

Будь-яка коректна рекурсивна функція повинна містити два структурних елементи:

1. Базовий випадок (base case) — умова, при якій функція повертає результат безпосередньо, без подальших рекурсивних викликів. Це «дно» рекурсії, звідки починається розгортання результатів.
2. Рекурсивний крок — виклик самої функції з аргументом, що наближає задачу до базового випадку. Кожен виклик повинен зменшувати складність задачі, щоб зрештою досягти базового випадку.

Якщо відсутній базовий випадок або рекурсивний крок ніколи не наближається до нього — функція рекурсуватиме нескінченно і призведе до StackOverflowException.

Рекурсивна функція факторіалу

Факторіал числа n визначається як добуток усіх натуральних чисел від 1 до n: n! = 1 × 2 × … × n. Математично його можна виразити рекурентно: n! = n × (n-1)!, і ця формула безпосередньо відображається у рекурсивному методі:

Базовий випадок — n == 1, де відоме значення без обчислення. Рекурсивний крок передає n - 1, наближаючись до бази з кожним викликом.

Поетапне розгортання: як виконується Factorial(4)

Щоб зрозуміти механізм рекурсії, розглянемо крок за кроком що відбувається при виклику Factorial(4):

1. Factorial(4): n ≠ 1, виконується return 4 * Factorial(3) — чекає результату
2. Factorial(3): n ≠ 1, виконується return 3 * Factorial(2) — чекає результату
3. Factorial(2): n ≠ 1, виконується return 2 * Factorial(1) — чекає результату
4. Factorial(1): n == 1, базовий випадок — повертає 1

Тепер стек розгортається у зворотньому напрямку:

• Factorial(2) отримує 1, повертає 2 × 1 = 2
• Factorial(3) отримує 2, повертає 3 × 2 = 6
• Factorial(4) отримує 6, повертає 4 × 6 = 24

Фактично виконується: 4 × 3 × 2 × 1 = 24.

Кожен активний виклик функції займає місце на стеку викликів і зберігає свій локальний контекст (значення n, адресу повернення). Після досягнення базового випадку стек починає «розкручуватись» — кожна функція отримує результат від нижньої та повертає свій.

Рекурсивна функція Фібоначчі

Числа Фібоначчі — ще один класичний приклад рекурсії. Послідовність визначається формулою f(n) = f(n-1) + f(n-2), де f(0) = 0, f(1) = 1. Перші члени: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34…

Тут два базових випадки: f(0) = 0 і f(1) = 1. Рекурсивний крок розбиває задачу на два менших підзавдання. Зверніть увагу: для Fibonacci(5) деякі підзавдання обчислюються повторно — наприклад, Fibonacci(2) викликається кілька разів. Це класична проблема наївної рекурсії Фібоначчі, де кількість викликів зростає експоненційно.

Рекурсія та цикли — порівняння

Більшість рекурсивних алгоритмів можна переписати через цикл. Ось варіант Фібоначчі без рекурсії:

Варіант із циклом виконується за лінійний час O(n) замість O(2ⁿ) у наївній рекурсії. Жодного повторного обчислення, жодних витрат на стек.

Коли рекурсія виправдана

Рекурсія не є поганим підходом — вона є природним і виразним рішенням для певного класу задач:

• Ієрархічні структури: обхід дерева каталогів, XML/JSON-документа, дерева виразів. Ітеративний обхід таких структур вимагає ручного управління власним стеком — рекурсія робить це автоматично.
• Алгоритми «розділяй і володарюй»: злиттєве сортування (merge sort), швидке сортування (quicksort), бінарний пошук у рекурсивному записі — усі вони природно розбивають задачу на підзадачі.
• Математичні означення, що мають рекурентну форму: якщо сама задача визначена рекурентно (як факторіал чи Фібоначчі), рекурсивний код читається як пряме відображення означення.

У прикладному коді медичної інформаційної системи рекурсія може знадобитись при обході ієрархії підрозділів лікарні, де кожен відділ може мати вкладені підвідділи довільної глибини. Ітерувати таку структуру через цикл значно складніше, ніж обійти рекурсивно.

Для лінійних задач — підсумовування масиву, пошук максимуму, послідовна обробка — цикл завжди кращий вибір: він швидший, використовує менше пам'яті і не загрожує StackOverflowException при великих вхідних даних.