Рекурсивные деревья помогают в анализе алгоритмов, позволяя оценить их трудоёмкость. 15 Для этого строится полное дерево рекурсии — граф, вершинами которого являются наборы фактических параметров при всех вызовах функции, начиная с первого обращения к ней, а рёбрами — пары таких наборов, соответствующие взаимным вызовам. 1

Некоторые характеристики, которые помогают оценить рекурсивный алгоритм по дереву рекурсии:

• Глубина рекурсивных вызовов. 1 Наибольшее одновременное количество рекурсивных обращений функции, определяющее максимальное количество слоёв рекурсивного стека, в котором осуществляется хранение отложенных вычислений. 1
• Объём рекурсии. 1 Одна из характеристик сложности рекурсивных вычислений для конкретного набора параметров, представляющая собой количество вершин полного рекурсивного дерева без единицы. 1

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