← JavaScript/Рекурсия#91 из 383← ПредыдущийСледующий →+30 XP
Полезно по теме:Гайд: как учить JavaScriptПрактика: JS базаПрактика: async и сетьТермин: Closure

Рекурсия

Какую проблему решает рекурсия

Ты работаешь с Notion или файловой системой: папка содержит подпапки, те — ещё подпапки, и так до любой глубины. Как обойти всё дерево, не зная заранее его глубину? Цикл for здесь бесполезен — он плоский.

Рекурсия — функция вызывает саму себя. Это идеальный инструмент для структур, которые по природе своей вложены: деревья, вложенные категории, DOM, JSON произвольной глубины.

На основе предыдущих уроков

  • «Функции» — рекурсия это просто функция, вызывающая себя
  • «if/else» — базовый случай — это условие остановки
  • «Массивы» — .reduce() и .push() — для накопления результатов

    • Два обязательных элемента рекурсии

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

    1. Базовый случай (base case) — условие остановки. Без него — бесконечный цикл.

    2. Рекурсивный случай — вызов себя с упрощённым аргументом.

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

// Как это работает:
// 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

    Рекурсия для древовидных структур

    Это главный практический сценарий:

    // Вложенные категории (как в интернет-магазине)
const categories = [
  { id: 1, name: 'Электроника', children: [
    { id: 2, name: 'Ноутбуки', children: [] },
    { id: 3, name: 'Смартфоны', children: [
      { id: 4, name: 'Apple', children: [] },
    ]},
  ]},
]

// Плоский обход дерева — цикл не знает глубины, рекурсия — знает
function flatten(nodes, depth = 0) {
  return nodes.reduce((acc, node) => {
    acc.push({ ...node, depth, children: undefined })
    if (node.children?.length) {
      acc.push(...flatten(node.children, depth + 1))
    }
    return acc
  }, [])
}

flatten(categories).forEach(c =>
  console.log('  '.repeat(c.depth) + c.name)
)
// 'Электроника'
// '  Ноутбуки'
// '  Смартфоны'
// '    Apple'

    Мемоизация: Фибоначчи

    Наивная рекурсия для Фибоначчи — экспоненциальное время O(2^n):

    // Медленно: fib(40) делает ~300 миллионов вызовов!
function fib(n) {
  if (n <= 1) return n
  return fib(n - 1) + fib(n - 2)  // одни и те же вычисления повторяются
}

// Мемоизация — кешируем уже вычисленные значения: O(n)
function fibMemo(n, memo = {}) {
  if (n in memo) return memo[n]
  if (n <= 1) return n
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo)
  return memo[n]
}

console.log(fibMemo(50))  // 12586269025 — мгновенно

    Стек вызовов и ограничения

    Каждый рекурсивный вызов добавляет кадр в стек. При глубине > ~10000 — переполнение:

    // Опасно для больших n:
function sumTo(n) {
  if (n === 0) return 0
  return n + sumTo(n - 1)  // при n = 100000 — Stack Overflow!
}

// Итеративный вариант — без ограничений стека:
function sumToIter(n) {
  let result = 0
  for (let i = 1; i <= n; i++) result += i
  return result
}

    Типичные ошибки

    1. Нет базового случая — бесконечная рекурсия:

    // Сломано — Stack Overflow:
function countdown(n) {
  console.log(n)
  countdown(n - 1)  // нет условия остановки!
}

// Исправлено:
function countdown(n) {
  if (n <= 0) return  // базовый случай
  console.log(n)
  countdown(n - 1)
}

    2. Базовый случай недостижим:

    // Сломано — n всегда увеличивается, никогда не достигнет 1:
function bad(n) {
  if (n === 1) return   // базовый случай есть, но...
  return bad(n + 1)     // n растёт! Stack Overflow при любом n > 1
}

// Исправлено — рекурсивный вызов должен УПРОЩАТЬ задачу:
function good(n) {
  if (n <= 1) return
  return good(n - 1)  // n уменьшается → придём к базовому случаю
}

    3. Используют рекурсию там, где нужна итерация:

    // Избыточно — простой цикл лучше:
function sumArray(arr, i = 0) {
  if (i === arr.length) return 0
  return arr[i] + sumArray(arr, i + 1)
}

// Проще и быстрее:
const sum = arr.reduce((a, b) => a + b, 0)

    В реальных проектах

  • Файловые системы: обход директорий в Node.js (fs.readdirSync рекурсивно)
  • DOM: обход дерева компонентов в React reconciler
  • JSON: глубокое копирование, поиск по вложенным полям
  • Категории: Ozon, Wildberries — дерево категорий товаров
  • Алгоритмы: быстрая сортировка, бинарный поиск — divide & conquer

    • Примеры

    Рекурсивный обход дерева категорий и поиск по вложенной структуре

    // Дерево категорий (как в Ozon или Wildberries)
const catalog = [
  {
    id: 1, name: 'Электроника',
    children: [
      { id: 2, name: 'Ноутбуки', children: [
        { id: 3, name: 'Apple MacBook', children: [] },
        { id: 4, name: 'Lenovo ThinkPad', children: [] },
      ]},
      { id: 5, name: 'Смартфоны', children: [
        { id: 6, name: 'iPhone', children: [] },
        { id: 7, name: 'Samsung Galaxy', children: [] },
      ]},
    ],
  },
  {
    id: 8, name: 'Одежда',
    children: [
      { id: 9, name: 'Мужская', children: [
        { id: 10, name: 'Футболки', children: [] },
      ]},
    ],
  },
]

// 1. Плоский список с уровнями вложенности
function flattenTree(nodes, level = 0) {
  return nodes.reduce((acc, node) => {
    acc.push({ id: node.id, name: node.name, level })
    if (node.children?.length) {
      acc.push(...flattenTree(node.children, level + 1))
    }
    return acc
  }, [])
}

console.log('=== Дерево категорий ===')
flattenTree(catalog).forEach(c =>
  console.log('  '.repeat(c.level) + c.name)
)

// 2. Поиск категории по id (любая глубина)
function findById(nodes, id) {
  for (const node of nodes) {
    if (node.id === id) return node
    const found = findById(node.children, id)
    if (found) return found
  }
  return null
}

const iphone = findById(catalog, 6)
console.log('\nНашли:', iphone?.name)  // 'iPhone'

const missing = findById(catalog, 999)
console.log('Не найдено:', missing)    // null

// 3. Подсчёт листьев (категорий без детей)
function countLeaves(nodes) {
  return nodes.reduce((count, node) => {
    if (!node.children?.length) return count + 1
    return count + countLeaves(node.children)
  }, 0)
}

console.log('\nКонечных категорий:', countLeaves(catalog))  // 7

    Рекурсия

    Какую проблему решает рекурсия

    Ты работаешь с Notion или файловой системой: папка содержит подпапки, те — ещё подпапки, и так до любой глубины. Как обойти всё дерево, не зная заранее его глубину? Цикл for здесь бесполезен — он плоский.

    Рекурсия — функция вызывает саму себя. Это идеальный инструмент для структур, которые по природе своей вложены: деревья, вложенные категории, DOM, JSON произвольной глубины.

    На основе предыдущих уроков

  • «Функции» — рекурсия это просто функция, вызывающая себя
  • «if/else» — базовый случай — это условие остановки
  • «Массивы» — .reduce() и .push() — для накопления результатов

    • Два обязательных элемента рекурсии

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

    1. Базовый случай (base case) — условие остановки. Без него — бесконечный цикл.

    2. Рекурсивный случай — вызов себя с упрощённым аргументом.

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

// Как это работает:
// 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

    Рекурсия для древовидных структур

    Это главный практический сценарий:

    // Вложенные категории (как в интернет-магазине)
const categories = [
  { id: 1, name: 'Электроника', children: [
    { id: 2, name: 'Ноутбуки', children: [] },
    { id: 3, name: 'Смартфоны', children: [
      { id: 4, name: 'Apple', children: [] },
    ]},
  ]},
]

// Плоский обход дерева — цикл не знает глубины, рекурсия — знает
function flatten(nodes, depth = 0) {
  return nodes.reduce((acc, node) => {
    acc.push({ ...node, depth, children: undefined })
    if (node.children?.length) {
      acc.push(...flatten(node.children, depth + 1))
    }
    return acc
  }, [])
}

flatten(categories).forEach(c =>
  console.log('  '.repeat(c.depth) + c.name)
)
// 'Электроника'
// '  Ноутбуки'
// '  Смартфоны'
// '    Apple'

    Мемоизация: Фибоначчи

    Наивная рекурсия для Фибоначчи — экспоненциальное время O(2^n):

    // Медленно: fib(40) делает ~300 миллионов вызовов!
function fib(n) {
  if (n <= 1) return n
  return fib(n - 1) + fib(n - 2)  // одни и те же вычисления повторяются
}

// Мемоизация — кешируем уже вычисленные значения: O(n)
function fibMemo(n, memo = {}) {
  if (n in memo) return memo[n]
  if (n <= 1) return n
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo)
  return memo[n]
}

console.log(fibMemo(50))  // 12586269025 — мгновенно

    Стек вызовов и ограничения

    Каждый рекурсивный вызов добавляет кадр в стек. При глубине > ~10000 — переполнение:

    // Опасно для больших n:
function sumTo(n) {
  if (n === 0) return 0
  return n + sumTo(n - 1)  // при n = 100000 — Stack Overflow!
}

// Итеративный вариант — без ограничений стека:
function sumToIter(n) {
  let result = 0
  for (let i = 1; i <= n; i++) result += i
  return result
}

    Типичные ошибки

    1. Нет базового случая — бесконечная рекурсия:

    // Сломано — Stack Overflow:
function countdown(n) {
  console.log(n)
  countdown(n - 1)  // нет условия остановки!
}

// Исправлено:
function countdown(n) {
  if (n <= 0) return  // базовый случай
  console.log(n)
  countdown(n - 1)
}

    2. Базовый случай недостижим:

    // Сломано — n всегда увеличивается, никогда не достигнет 1:
function bad(n) {
  if (n === 1) return   // базовый случай есть, но...
  return bad(n + 1)     // n растёт! Stack Overflow при любом n > 1
}

// Исправлено — рекурсивный вызов должен УПРОЩАТЬ задачу:
function good(n) {
  if (n <= 1) return
  return good(n - 1)  // n уменьшается → придём к базовому случаю
}

    3. Используют рекурсию там, где нужна итерация:

    // Избыточно — простой цикл лучше:
function sumArray(arr, i = 0) {
  if (i === arr.length) return 0
  return arr[i] + sumArray(arr, i + 1)
}

// Проще и быстрее:
const sum = arr.reduce((a, b) => a + b, 0)

    В реальных проектах

  • Файловые системы: обход директорий в Node.js (fs.readdirSync рекурсивно)
  • DOM: обход дерева компонентов в React reconciler
  • JSON: глубокое копирование, поиск по вложенным полям
  • Категории: Ozon, Wildberries — дерево категорий товаров
  • Алгоритмы: быстрая сортировка, бинарный поиск — divide & conquer

    • Примеры

    Рекурсивный обход дерева категорий и поиск по вложенной структуре

    // Дерево категорий (как в Ozon или Wildberries)
const catalog = [
  {
    id: 1, name: 'Электроника',
    children: [
      { id: 2, name: 'Ноутбуки', children: [
        { id: 3, name: 'Apple MacBook', children: [] },
        { id: 4, name: 'Lenovo ThinkPad', children: [] },
      ]},
      { id: 5, name: 'Смартфоны', children: [
        { id: 6, name: 'iPhone', children: [] },
        { id: 7, name: 'Samsung Galaxy', children: [] },
      ]},
    ],
  },
  {
    id: 8, name: 'Одежда',
    children: [
      { id: 9, name: 'Мужская', children: [
        { id: 10, name: 'Футболки', children: [] },
      ]},
    ],
  },
]

// 1. Плоский список с уровнями вложенности
function flattenTree(nodes, level = 0) {
  return nodes.reduce((acc, node) => {
    acc.push({ id: node.id, name: node.name, level })
    if (node.children?.length) {
      acc.push(...flattenTree(node.children, level + 1))
    }
    return acc
  }, [])
}

console.log('=== Дерево категорий ===')
flattenTree(catalog).forEach(c =>
  console.log('  '.repeat(c.level) + c.name)
)

// 2. Поиск категории по id (любая глубина)
function findById(nodes, id) {
  for (const node of nodes) {
    if (node.id === id) return node
    const found = findById(node.children, id)
    if (found) return found
  }
  return null
}

const iphone = findById(catalog, 6)
console.log('\nНашли:', iphone?.name)  // 'iPhone'

const missing = findById(catalog, 999)
console.log('Не найдено:', missing)    // null

// 3. Подсчёт листьев (категорий без детей)
function countLeaves(nodes) {
  return nodes.reduce((count, node) => {
    if (!node.children?.length) return count + 1
    return count + countLeaves(node.children)
  }, 0)
}

console.log('\nКонечных категорий:', countLeaves(catalog))  // 7

    Задание

    Ты разрабатываешь бэкенд для Notion-подобного приложения. Страницы имеют вложенную структуру: каждая страница может содержать дочерние страницы произвольной глубины. Реализуй: 1. `countPages(pages)` — рекурсивно считает общее количество страниц (включая вложенные) 2. `findPage(pages, id)` — рекурсивно ищет страницу по id, возвращает её или null 3. `getPath(pages, id)` — возвращает массив названий от корня до найденной страницы

    Подсказка

    countPages: count + 1 + countPages(page.children). findPage: findPage(page.children, id). getPath: getPath(page.children, id, current). Для getPath — передавай накапливаемый массив current в рекурсию.

    Загружаем среду выполнения...
    Загружаем AI-помощника...