Що означає "глибина рекурсії"?

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

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

Глибина рекурсії - це кількість одночасно активних рекурсивних викликів (глибина стека викликів) у процесі виконання алгоритму; також часто під нею розуміють максимально можливу чи фактичну максимальну глибину таких викликів для конкретного входу. Від глибини рекурсії напряму залежить споживання стека (пам'ять) і ризик переповнення стека.

Детальна відповідь

Визначення

Поточна глибина рекурсії: скільки кадрів (frames) рекурсивної функції одночасно перебуває в стеку в даний момент виконання.
Максимальна глибина рекурсії: найбільше значення поточної глибини за час роботи алгоритму на даному вході. Її часто використовують для оцінки витрат пам'яті і надійності рішення.

Чому це важливо

Пам'ять стека: кожен рекурсивний виклик утримує локальні змінні і адресу повернення. Пам'ять на стеку зростає пропорційно глибині: O(depth).
Переповнення стека: якщо глибина перевищить ліміт середовища/мови, програма впаде з помилкою переповнення стека.
Асимптотика: глибина рекурсії часто дорівнює природній мірі задачі (розмір входу, висота дерева, log n тощо) і визначає просторову складність.

Приклади коду

Приклад 1: факторіал з вимірюванням максимальної глибини в JavaScript.

function fact(n, depth = 1, stats = { maxDepth: 0 }) {
  stats.maxDepth = Math.max(stats.maxDepth, depth);
  if (n <= 1) return 1;
  return n * fact(n - 1, depth + 1, stats);
}

const stats = { maxDepth: 0 };
console.log(fact(5, 1, stats)); // 120
console.log('maxDepth =', stats.maxDepth); // 5
// Максимальна глибина для fact(n) дорівнює n (лінійна рекурсія).

Приклад 2: обчислення висоти (максимальної глибини) N-арного дерева в Python - глибина рекурсії дорівнює висоті дерева.

class Node:
    def __init__(self, val, children=None):
        self.val = val
        self.children = children or []

def max_depth(root, depth=1):
    if root is None:
        return 0
    if not root.children:
        return depth
    return max(max_depth(c, depth + 1) for c in root.children)

root = Node(1, [Node(2), Node(3, [Node(4)])])
print(max_depth(root))  # 3
# Глибина рекурсії при обході дерева дорівнює висоті дерева.

Оцінка глибини рекурсії для типових задач

Лінійна рекурсія (факторіал, підрахунок суми 1..n): глибина = n → O(n).
Бінарний пошук: глибина ≈ ⌊log2 n⌋ → O(log n).
Обхід дерева (DFS): глибина = висота дерева h → O(h). Для незбалансованого дерева h може бути O(n).
Швидке сортування: середня глибина = O(log n), у найгіршому випадку = O(n) (при поганому виборі опорного елемента).

Глибина рекурсії і складність за пам'яттю

Просторова складність рекурсивного алгоритму зазвичай дорівнює O(depth), оскільки одночасно в стеку перебуває глибина кадрів виклику. Приблизне споживання пам'яті можна оцінити як: пам'ять ≈ розмір_кадру × depth.

Розмір кадру включає локальні змінні, параметри, адресу повернення і службові дані рантайму.
Хвостова рекурсія за наявності оптимізації може утримувати O(1) стека, оскільки кадр перевикористовується.

Хвостова рекурсія і оптимізація

Хвостовий виклик - це рекурсивний виклик, що є останньою операцією функції. За підтримки оптимізації хвостових викликів (TCO) глибина рекурсії логічно може бути великою, але фізично стек залишається O(1). Однак у багатьох популярних середовищах TCO або недоступна, або не гарантована.

Надійний підхід для глибокої рекурсії: переписати в ітеративний алгоритм з явним стеком/циклом.

Порівняння хвостової та ітеративної версій на прикладі суми 1..n в JavaScript.

function sumRange(n, acc = 0) {
  if (n === 0) return acc; // хвостовий виклик
  return sumRange(n - 1, acc + n);
}

// Ітеративно (надійніше для великих n):
function sumRangeIter(n) {
  let acc = 0;
  while (n > 0) {
    acc += n;
    n--;
  }
  return acc;
}

console.log(sumRange(5));     // 15
console.log(sumRangeIter(5)); // 15

Обмеження і практичні поради

Контролюйте базовий випадок. Він повинен гарантовано спрацьовувати і зменшувати глибину; інакше можлива нескінченна рекурсія.
Оцінюйте найгіршу глибину на реальних даних: для незбалансованих структур вона може бути лінійною.
Налаштування/ліміти: в одних середовищах можна змінювати ліміт рекурсії чи розмір стека (наприклад, у деяких мовах/рантаймах), в інших - ні; враховуйте обмеження цільової платформи.
Для потенційно великої глибини використовуйте ітеративні рішення чи власний стек/чергу.
Не покладайтеся на TCO там, де вона не гарантована; розраховуйте на O(depth) за пам'яттю.

Як відповідати на співбесіді

Дати визначення: глибина рекурсії - кількість активних рекурсивних викликів і/або максимально досягнута глибина.
Згадати зв'язок зі стеком і просторовою складністю O(depth).
Навести приклад (факторіал/DFS) і сказати, від чого залежить глибина (n, висота дерева, log n).
Описати ризики переповнення стека і альтернативи (ітерація, власний стек, балансування, хвостова рекурсія).

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

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

Premium

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