Що таке рекурсія?

Рекурсія — це техніка в програмуванні, де функція викликає саму себе для вирішення проблеми.

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

Структура Рекурсивної Функції

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

Базовий випадок — умова, за якою функція зупиняє рекурсивні виклики.
Рекурсивний виклик — виклик самої себе з новими аргументами.

Приклад: Факторіал

Факторіал числа n (n!) — це добуток усіх натуральних чисел від 1 до n.

function factorial(n: number): number {
  if (n === 1) return 1;         // Базовий випадок
  return n * factorial(n - 1);   // Рекурсивний виклик
}

console.log(factorial(5)); // 120

Як це працює

Виклик factorial(5) розгорнеться так:

matlab

factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1
= 120

Приклад: Перебір Масиву з Рекурсією

function printArray(arr: number[], index = 0): void {
  if (index >= arr.length) return;
  console.log(arr[index]);
  printArray(arr, index + 1);
}

printArray([10, 20, 30, 40]);

Рекурсія vs Ітерація

Характеристика	Рекурсія	Ітерація
Підхід	Функція викликає саму себе	Використовує цикли
Пам'ять	Використовує `Call Stack`	Більш ефективна по пам'яті
Складність розуміння	Часто складніша для початківців	Простішою та більш візуальною
Гнучкість	Добре підходить для рекурсивних структур (дерева, графи)	Відмінно підходить для послідовних операцій

Коли Використовувати Рекурсію?

Робота з деревами та графами (DOM, файлові системи, дерево компонентів)
Парсинг вкладених структур (наприклад, парсинг HTML або JSON)
Алгоритми: реверсний перебір, повернення, пошук шляхів

Будьте обережні з Переповненням Стеку:

Рекурсія може призвести до переповнення стека, якщо немає базового випадку або структура занадто глибоко вкладена.

Висновок

Рекурсія — це спосіб вирішення проблем шляхом неодноразового виклику функції на самій собі.
Завжди повинен бути базовий випадок для виходу.
Використовується там, де проблеми можуть бути розбиті на підпроблеми (особливо в структурах даних).

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.

Дочитали статтю?

Практика завдань

Що таке рекурсія?

#Структура Рекурсивної Функції

#Приклад: Факторіал

#Як це працює

#Приклад: Перебір Масиву з Рекурсією

#Рекурсія vs Ітерація

#Коли Використовувати Рекурсію?

#Висновок