Зачем нужна рекурсия?

Рекурсия в программировании

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

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

Функция является рекурсивной, если она вызывает сама себя с другими параметрами, пока не достигнет базового случая (условия остановки).

Зачем нужна рекурсия?

1. Решение задач с древовидной структурой

Рекурсия идеально подходит для работы с иерархическими данными:

// Подсчёт всех файлов в директориях
function countFiles(directory) {
  let count = 0;
  
  for (const item of directory.items) {
    if (item.isFile) {
      count++;
    } else if (item.isDirectory) {
      count += countFiles(item); // Рекурсивный вызов
    }
  }
  
  return count;
}

2. Обход DOM-элементов

В DOM часто нужно рекурсивно обойти все вложенные элементы:

function traverseDOM(element) {
  console.log(element);
  
  for (const child of element.children) {
    traverseDOM(child); // Обход дочерних элементов
  }
}

traverseDOM(document.body);

3. Работа с вложенными объектами и массивами

Поиск в глубоко вложенных структурах:

function findValueByKey(obj, key) {
  for (const k in obj) {
    if (k === key) {
      return obj[k];
    }
    if (typeof obj[k] === "object" && obj[k] !== null) {
      const result = findValueByKey(obj[k], key);
      if (result !== undefined) {
        return result;
      }
    }
  }
}

4. Математические вычисления

Факториал, числа Фибоначчи, степень числа:

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

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

// Числа Фибоначчи
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

Компоненты рекурсии

Базовый случай (Base case) - условие, при котором рекурсия останавливается:

if (n === 0) return 1; // Без этого будет бесконечная рекурсия

Рекурсивный случай - вызов функции с упрощённым параметром:

return n * factorial(n - 1); // n-1 ближе к базовому случаю

Преимущества рекурсии

• Естественное решение для задач с рекурсивной структурой
• Меньше кода - часто компактнее итеративного подхода
• Легче понять логику - отражает суть задачи

Недостатки и подводные камни

Stack overflow - при глубокой рекурсии память переполняется:

function deepRecursion(n) {
  if (n === 0) return;
  deepRecursion(n - 1); // При n > ~10000 ошибка!
}

Производительность - повторные вычисления без оптимизации:

// Медленно: fibonacci(40) вычисляется долго
function slowFibonacci(n) {
  if (n <= 1) return n;
  return slowFibonacci(n - 1) + slowFibonacci(n - 2);
}

// Быстро: с мемоизацией
const memo = {};
function fastFibonacci(n) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  memo[n] = fastFibonacci(n - 1) + fastFibonacci(n - 2);
  return memo[n];
}

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

• Работа с древовидными структурами
• Обход графов и DOM
• Математические расчёты
• Задачи разделения и покорения (divide and conquer)

Для простых линейных операций лучше использовать циклы - они быстрее и безопаснее по памяти.