Глубина рекурсии
Глубина рекурсии — это максимальное число вложенных вызовов рекурсивной функции, которые существуют одновременно во время работы программы. Она показывает, насколько глубоко рекурсивный алгоритм может «погрузиться» в последовательность вызовов.
Как считать глубину
Нужно найти самый длинный путь последовательных вызовов функции до остановки рекурсии. Каждый новый вызов увеличивает текущую глубину на единицу, а после возврата из него глубина уменьшается. Ветви, которые выполняются по очереди, не складываются: одновременно учитывается только одна активная цепочка.
Рассмотрим функцию, которая при \(n>0\) вызывает себя с аргументом \(n-1\), а при \(n=0\) завершает работу. При начальном вызове \(f(3)\) активны цепочки \(f(3) \to f(2) \to f(1) \to f(0)\). Поэтому глубина рекурсии равна \(4\): учитывается и первоначальный вызов \(f(3)\).
Глубина рекурсии — не то же самое, что общее число вызовов. Например, при двух рекурсивных вызовах из каждого состояния общее число вызовов может быть большим, но глубина определяется только длиной самой длинной цепочки. Размер дерева рекурсивных вызовов и глубина — разные характеристики.
Функция вызывает себя для \(n-1\), пока не достигает \(n=0\). Какова глубина при начальном вызове \(f(5)\)?
При анализе программы глубину сравнивают с доступной памятью: каждый активный вызов занимает место в стеке рекурсивных вызовов. Если цепочка слишком длинная, может возникнуть переполнение стека. В задачах важно указать, считается ли начальный вызов: обычно он включается в глубину.
Главное
- Глубина рекурсии — максимальное число одновременно активных вложенных вызовов.
- Начальный вызов и вызов базового случая обычно считаются.
- Глубина не равна общему числу вызовов или размеру дерева рекурсии.