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

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

Классический пример — вычисление факториала. Факториал n (n!) — это n * (n-1)!. Для n=1 ответ 1 (базовый случай). Для n>1 — вызываем себя с n-1:

function factorial(n) {
  if (n <= 1) return 1;  // базовый случай
  return n * factorial(n - 1);  // рекурсивный вызов
}

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

Здесь каждый вызов ждёт результат следующего, пока не дойдёт до базы, потом значения возвращаются обратно по цепочке.

Важные моменты:

• Базовый случай обязателен. Без него рекурсия уйдёт в бесконечный цикл и упадёт с ошибкой переполнения стека (stack overflow).
• Стек вызовов. Каждый рекурсивный вызов кладётся в стек. Глубина рекурсии ограничена памятью — обычно ~10-15 тысяч вызовов в JavaScript, в Python ~1000. Для глубоких рекурсий используют хвостовую рекурсию (если язык её оптимизирует) или заменяют циклом.
• Где использовать: обход деревьев (DOM, файловая система), алгоритмы с ветвлением (поиск в глубину, задача о ханойских башнях), разбор грамматик. Но для простых итераций (сумма массива, факториал) цикл компактнее и быстрее — рекурсия добавляет накладные расходы на вызовы.

Пример с обходом дерева папок:

function listFiles(dir) {
  const entries = fs.readdirSync(dir, { withFileTypes: true });
  for (const entry of entries) {
    const fullPath = path.join(dir, entry.name);
    if (entry.isDirectory()) {
      listFiles(fullPath);  // рекурсия для подпапок
    } else {
      console.log(fullPath);
    }
  }
}

Здесь базовый случай — когда в папке нет вложенных директорий (цикл просто выводит файлы).

Итог: рекурсия — мощный инструмент для задач с самоподобной структурой, но требует контроля глубины и явного базового случая. На собеседовании обычно проверяют понимание стека и умение переписать рекурсию в цикл.