Приведи пример использования рекурсии

Пример использования рекурсии

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

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

Каждая рекурсивная функция должна иметь:

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

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

Классический пример для изучения рекурсии:

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

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

Пример 2: Обход дерева объектов

Это практическое применение в React и обработке данных:

const menu = {
  name: "Меню",
  children: [
    {
      name: "Файл",
      children: [
        { name: "Новый" },
        { name: "Открыть" }
      ]
    },
    {
      name: "Правка",
      children: [
        { name: "Копировать" },
        { name: "Вставить" }
      ]
    }
  ]
};

function printMenu(item, level = 0) {
  // Вывод текущего пункта
  console.log(" ".repeat(level * 2) + item.name);
  
  // Рекурсивный вызов для детей
  if (item.children) {
    item.children.forEach(child => printMenu(child, level + 1));
  }
}

printMenu(menu);
// Вывод:
// Меню
//   Файл
//     Новый
//     Открыть
//   Правка
//     Копировать
//     Вставить

Пример 3: Поиск в глубину (DFS) в графе

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A"],
  D: ["B"]
};

function dfs(node, visited = new Set()) {
  if (visited.has(node)) return;
  
  visited.add(node);
  console.log(node);
  
  // Рекурсивный обход соседних узлов
  for (const neighbor of graph[node]) {
    dfs(neighbor, visited);
  }
}

dfs("A"); // A B D C

Пример 4: Копирование вложенного объекта

Опасный пример, показывающий применение рекурсии в реальном коде React:

function deepClone(obj) {
  // Базовые типы
  if (obj === null || typeof obj !== "object") {
    return obj;
  }
  
  // Массивы
  if (Array.isArray(obj)) {
    return obj.map(item => deepClone(item));
  }
  
  // Объекты
  const cloned = {};
  for (const key in obj) {
    if (obj.hasOwnProperty(key)) {
      cloned[key] = deepClone(obj[key]); // Рекурсивный вызов
    }
  }
  return cloned;
}

const original = { a: 1, b: { c: 2 } };
const copy = deepClone(original);
copy.b.c = 999;
console.log(original.b.c); // 2 - оригинал не изменился

Пример 5: Сумма элементов вложенного массива

function sumArray(arr) {
  let sum = 0;
  
  for (const item of arr) {
    if (Array.isArray(item)) {
      sum += sumArray(item); // Рекурсивный вызов для подмассива
    } else if (typeof item === "number") {
      sum += item;
    }
  }
  
  return sum;
}

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

Пример 6: Обратный вывод строки

Простой, но красивый пример:

function reverse(str) {
  // Базовый случай
  if (str.length <= 1) return str;
  
  // Рекурсивный случай
  return reverse(str.slice(1)) + str[0];
}

console.log(reverse("Привет")); // "тевирП"

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

• Обход деревьев и графов — идеален для структур данных с переменной глубиной
• Парсинг и компиляция — разбор вложенных выражений
• Динамическое программирование — решение подзадач
• Работа с файловой системой — обход папок

Когда избегать рекурсии

• Глубокие рекурсии — может привести к переполнению стека (stack overflow)
• Простые циклические задачи — for/while быстрее и понятнее
• Оптимизация памяти критична — каждый вызов занимает память стека

Оптимизация: мемоизация

Для рекурсивных функций, вызываемых множество раз с теми же параметрами:

const memo = {};

function fibMemo(n) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  
  memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
  return memo[n];
}

console.log(fibMemo(50)); // Очень быстро

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