Як рекурсія впливає на просторову складність?

АлгоритмиJunior~2 хв читання

Коротка відповідь

Рекурсія підвищує просторову складність через додатковий стек викликів: кожна активація функції займає пам'ять під локальні змінні і адресу повернення. Зазвичай це O(h), де h - глибина рекурсії. Для лінійної рекурсії h=O(n), для двійкової - h дорівнює висоті рекурсивного дерева (часто O(log n) в алгоритмах «розділяй і володарюй»). Без оптимізації хвостової рекурсії пам'ять не звільняється до згортання викликів; при TCO хвостова рекурсія може мати O(1) стек.

Детальне пояснення

Як формується просторова складність при рекурсії

Стек викликів: кожен рекурсивний виклик створює фрейм зі своїми локальними даними.
Глибина рекурсії h: максимальна кількість одночасно «живих» викликів визначає додаткову пам'ять O(h).
Додаткові структури: окрім стека, алгоритм може використовувати масиви/кеші, що додає пам'ять до загальної оцінки.

Базовий приклад: лінійна рекурсія проти ітерації

Факторіал: рекурсивне рішення використовує O(n) стека, ітеративне - O(1).

// JavaScript
function factRec(n) {
  if (n <= 1) return 1;      // глибина стека: n
  return n * factRec(n - 1); // просторова складність за стеком: O(n)
}

function factIter(n) {
  let res = 1;               // O(1) додаткової пам'яті
  for (let i = 2; i <= n; i++) res *= i;
  return res;
}

Двійкова рекурсія: глибина проти кількості викликів

Наївний Fibonacci робить експоненційно багато викликів, але глибина стека залишається O(n). Просторова складність за стеком визначається саме глибиною, а не кількістю всіх викликів.

// JavaScript
function fib(n) {
  if (n <= 1) return n;      // глибина стека: n
  return fib(n - 1) + fib(n - 2); // кількість викликів експоненційна, але стек: O(n)
}

Розділяй і володарюй: типові оцінки

Quicksort: середня глибина рекурсії O(log n) → стек O(log n); найгірший випадок - O(n). Додаткових структур немає (крім стека), якщо сортуємо на місці.
Mergesort (top-down): стек O(log n) за глибиною, але потрібен додатковий допоміжний масив O(n), що домінує.
Бінарний пошук: рекурсивна глибина O(log n) → стек O(log n). Ітеративна версія - O(1).

Дерева/графи: DFS рекурсивно та ітеративно

Рекурсивний DFS використовує стек викликів O(h), де h - висота дерева/довжина шляху; ітеративний варіант використовує явний стек тієї самої асимптотики, але контрольований у купі.

// JavaScript: DFS по дереву
function dfsRec(node) {
  if (!node) return; // стек: O(h)
  process(node);
  for (const child of node.children) dfsRec(child);
}

function dfsIter(root) {
  const stack = [root];      // явний стек: O(h)
  while (stack.length) {
    const node = stack.pop();
    if (!node) continue;
    process(node);
    // щоб порядок збігався з рекурсією, додаємо дітей у зворотному порядку
    for (let i = node.children.length - 1; i >= 0; i--) {
      stack.push(node.children[i]);
    }
  }
}

Хвостова рекурсія і TCO

Без оптимізації хвостової рекурсії (TCO) навіть хвостові виклики накопичують стек → O(n).
За ввімкненого TCO компілятор перевикористовує один фрейм → стек O(1).
Підтримка TCO залежить від мови/компілятора/прапорців; у багатьох середовищах веброзробки (наприклад, типовий JS рантайм) TCO не гарантована.

// Хвостова рекурсія (теоретично TCO → O(1), інакше O(n))
function sumRecTail(arr, i = 0, acc = 0) {
  if (i === arr.length) return acc; // хвостовий виклик
  return sumRecTail(arr, i + 1, acc + arr[i]);
}

// Еквівалентна ітерація - завжди O(1)
function sumIter(arr) {
  let acc = 0;
  for (let i = 0; i < arr.length; i++) acc += arr[i];
  return acc;
}

Врахування додаткової пам'яті (кеші, буфери)

Якщо рекурсія використовує мемоізацію чи тимчасові буфери, загальна просторова складність - це сума: стек O(h) плюс пам'ять під кеш/буфер. Наприклад, динамічне програмування по масиву з мемоізацією дає O(n) пам'яті понад стек.

Практичні висновки для співбесіди

Визначайте максимальну глибину рекурсії h - саме вона задає споживання стека.
Враховуйте допоміжні структури даних: вони можуть домінувати (як у mergesort).
Порівнюйте з ітерацією: рекурсію часто можна переписати на цикл з явним стеком/чергою, зберігши асимптотику за часом і контролюючи пам'ять.
Оцінюйте найгірший випадок: у quicksort стек може вирости до O(n).
Знайте про TCO, але не покладайтеся на неї, якщо середовище не гарантує оптимізацію.

Підсумок

Рекурсія додає до просторової складності витрати стека O(h), де h - максимальна глибина рекурсивних викликів. В одних задачах це O(n), в інших - O(log n); у найгірших випадках можливо O(n) і переповнення стека. Ітеративні версії й оптимізації (TCO, хвостова рекурсія, явні структури) допомагають тримати пам'ять під контролем.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.