Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Що означає "глибина рекурсії"?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

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

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

### Визначення

- Поточна глибина рекурсії: скільки кадрів (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).
- Описати ризики переповнення стека і альтернативи (ітерація, власний стек, балансування, хвостова рекурсія).

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати686 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.