Задание № 25 · ЕГЭ

Размер дерева рекурсивных вызовов

Как оценить число вызовов и уровней в рекурсивном алгоритме

2 мин чтенияСложность: Обновлено 29 сентября 2026

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

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

Как считают размер

Корень дерева — исходный вызов функции. Если каждый вызов порождает \(b\) новых вызовов, а максимальная глубина равна \(h\), то число узлов можно оценить как сумму по уровням. Для полного \(b\)-ичного дерева на уровне \(i\) находится \(b^i\) узлов: на нулевом уровне — один корень, на первом — \(b\) вызовов и так далее. Такое представление является частью общего дерева рекурсивных вызовов.

\[N = \sum_{i=0}^{h} b^i = \frac{b^{h+1}-1}{b-1},\quad b\ne 1\]

Здесь \(N\) — общее число узлов, \(b\) — число дочерних вызовов у каждого узла, а \(h\) — номер последнего уровня, считая корень уровнем \(0\). Если \(b=1\), дерево превращается в цепочку, поэтому \(N=h+1\). В реальной программе ветвление может быть неодинаковым, тогда формулу используют как оценку или считают узлы по уровням отдельно.

№

Пример

Пусть каждый вызов порождает \(2\) новых вызова, а рекурсия заканчивается на глубине \(3\). Число узлов равно \(1+2+4+8=15\). Значит, функция была вызвана 15 раз, хотя одновременно активными являются только вызовы одной цепочки.

Не путайте размер и глубину

Размер дерева — это общее количество вызовов, то есть всех узлов. Глубина — длина самой длинной цепочки вложенных вызовов. У бинарного дерева глубины \(h\) размер может быть около \(2^{h+1}\), поэтому эти величины нельзя заменять друг другом. Также число листьев не равно числу всех вызовов: внутренние узлы тоже считаются.

Проверьте себя

Полное троичное дерево рекурсивных вызовов имеет глубину \(2\), корень находится на уровне \(0\). Сколько в нём узлов?

Главное за минуту

Главное

Размер дерева — общее число вызовов, или узлов; исходный вызов также учитывается.
Для полного \(b\)-ичного дерева глубины \(h\): \(N=\sum_{i=0}^{h}b^i\).
Глубина показывает вложенность вызовов, а размер — их общее количество; при ветвлении размер обычно растёт быстрее.