Что такое рекурсия?

Рекурсия — это техника в программировании, при которой функция вызывает саму себя для решения задачи.

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

Структура рекурсивной функции

Любая рекурсивная функция должна содержать два основных элемента:

1. Базовый случай (base case) — условие, при котором функция прекращает рекурсивные вызовы.
2. Рекурсивный вызов — вызов самой себя с новыми аргументами.

Пример: Факториал числа

Факториал числа 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) будет развёрнут так:

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 Итерация

Когда использовать рекурсию?

• Работа с деревьями и графами (DOM, файловая система, дерево компонентов)
• Разбор вложенных структур (например, парсинг HTML или JSON)
• Алгоритмы: обратный обход, перебор вариантов (backtracking), поиск путей

Вывод

• Рекурсия — это способ решения задач путём повторного вызова функции самой себя.
• Всегда должен быть базовый случай для выхода.
• Используется там, где задачи можно разбить на подзадачи (особенно в структурах данных).