Рекурсия и стек вызовов

Рекурсия — когда функция вызывает саму себя. Каждый вызов добавляется в стек вызовов. Без base case — бесконечная рекурсия (Stack Overflow). Рекурсия полезна для деревьев, поиска и задач, которые разбиваются на подзадачи.

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

Рекурсия — это функция, которая вызывает сама себя.

function countdown(n) { if (n === 0) { // base case — ОСТАНОВКА! console.log('Поехали!'); return; } console.log(n); countdown(n - 1); // рекурсивный вызов }

countdown(3); // 3, 2, 1, Поехали!

Base case — ОБЯЗАТЕЛЕН. Без него — бесконечная рекурсия.

Стек вызовов (Call Stack): Каждый вызов функции добавляется в стек (стопка). Когда функция завершается — она удаляется из стека.

countdown(3) → стек: [countdown(3)] countdown(2) → стек: [countdown(3), countdown(2)] countdown(1) → стек: [countdown(3), countdown(2), countdown(1)] countdown(0) → стек: [countdown(3), countdown(2), countdown(1), countdown(0)] Поехали! → countdown(0) завершается → countdown(1) завершается → countdown(2) завершается → countdown(3) завершается

Stack Overflow — когда стек переполняется (слишком много вложенных вызовов).

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

• Обход деревьев
• Поиск в глубину
• Задачи типа «разбей на подзадачи»

Когда использовать цикл:

• Простые итерации
• Когда важна производительность

Рекурсия — как матрёшка. Открываешь куклу — внутри ещё одна кукла. Открываешь её — ещё одна. Base case — когда внутри больше ничего нет.

**Самый простой:**

function factorial(n) {
  if (n <= 1) return 1; // base case
  return n * factorial(n - 1); // рекурсия
}

console.log(factorial(5)); // 120
// 5 * 4 * 3 * 2 * 1 = 120

factorial(5) = 5 * factorial(4) = 5 * 4 * factorial(3) = ...

**Простой:**

function sumArray(arr, index = 0) {
  if (index === arr.length) return 0; // base case
  return arr[index] + sumArray(arr, index + 1);
}

console.log(sumArray([1, 2, 3, 4])); // 10

Рекурсивное суммирование: берём первый элемент + сумма остальных.

**Реальный пример:**

function findDeep(obj, key) {
  if (key in obj) return obj[key];

  for (const value of Object.values(obj)) {
    if (typeof value === 'object' && value !== null) {
      const result = findDeep(value, key);
      if (result !== undefined) return result;
    }
  }
  return undefined;
}

const config = {
  app: { name: 'MyApp', settings: { theme: 'dark' } }
};

console.log(findDeep(config, 'theme')); // 'dark'

Рекурсивный поиск по вложенному объекту.

**Неправильно:** Забыть base case

**Почему:** Без base case — бесконечная рекурсия → Stack Overflow.

**Правильно:** Всегда начинайте с base case.

**Неправильно:** Использовать рекурсию для простых итераций

**Почему:** Рекурсия менее эффективна: каждый вызов добавляет в стек.

**Правильно:** Для простых циклов используйте for/while.

**Неправильно:** Не уменьшать аргументы при рекурсии

**Почему:** Если аргумент не приближается к base case — бесконечная рекурсия.

**Правильно:** Каждый рекурсивный вызов должен приближать к base case.

• Base case — ОБЯЗАТЕЛЕН для остановки
• Каждый вызов добавляется в стек вызовов
• Stack Overflow — стек переполнился
• Рекурсия → деревья, поиск, подзадачи
• Простые итерации → циклы

Назад: Вы знаете функции (J9) и this (JI4-JI5) — теперь вы понимаете, как функции вызывают друг друга.

Вперёд: Следующий урок (JI7) — геттеры и сеттеры для контролируемого доступа к свойствам.