Дерево рекурсивных вызовов
Дерево рекурсивных вызовов — это схема, показывающая, как один запуск рекурсивного алгоритма порождает другие запуски, а те — следующие вложенные вызовы. По дереву видно порядок разбиения задачи и количество возникающих ветвей.
Дерево строят сверху вниз. В корне записывают исходные параметры функции. Для каждого вызова определяют, какие рекурсивные вызовы он делает, и соединяют их с исходной вершиной. Если вызов не обращается к функции снова, он становится листом. Поэтому глубина дерева показывает максимальную глубину рекурсии, а число вершин — общее число вызовов.
Здесь \(T(n)\) — число вызовов для задачи размера \(n\), \(k\) — число рекурсивных ветвей, а \(n_i\) — размеры подзадач. Слагаемое \(1\) учитывает сам текущий вызов. Такая запись используется при анализе рекурсивного алгоритма, а подробный подсчёт количества вершин рассматривает размер дерева рекурсивных вызовов.
Пусть функция при \(n>1\) вызывает себя для \(n-1\) два раза, а при \(n=1\) останавливается. Для \(n=3\) дерево имеет вид: корень \(T(3)\); у него два потомка \(T(2)\); у каждого из них по два потомка \(T(1)\). Всего вызовов: \(1+2+4=7\). Одинаковые параметры у разных вершин всё равно означают разные вызовы.
Дерево показывает все вызовы, включая уже завершённые ветви. Стек рекурсивных вызовов показывает только цепочку вызовов, находящихся в работе в данный момент. Поэтому дерево может иметь много вершин, а размер стека в конкретный момент равен лишь глубине текущей ветви.
Рекурсивная функция делает по 2 вызова на каждом из 3 уровней, а затем останавливается. Сколько листьев будет в дереве?
Главное
- Корень дерева — исходный вызов, потомки — вложенные рекурсивные вызовы, листья — базовые случаи.
- Число вершин показывает общее количество вызовов, а глубина дерева связана с максимальным уровнем вложенности.
- Дерево вызовов описывает все ветви, а стек — только текущую незавершённую цепочку.