Сложность анализа рекурсивных алгоритмов связана с несколькими факторами:

• Высокая ресурсоёмкость. 1 При большом количестве самовызовов рекурсивных функций быстро заполняется стековая область. 1 Кроме того, организация хранения и закрытия очередного слоя рекурсивного стека — дополнительные операции, которые требуют временных затрат. 1
• Влияние количества итераций рекурсии. 2 Рекурсивная процедура может выглядеть достаточно простой, но она может серьёзно усложнить программу, многократно вызывая себя. 2 Особенно сложно анализировать алгоритмы с многократной рекурсией. 23
• Объёмная сложность. 23 При каждом вызове процедура запрашивает небольшой объём памяти в стеке для сохранения значений локальных переменных, но в сумме этот объём может занимать значительную часть доступной памяти. 2
• Необходимость учёта временной и пространственной сложности. 4 Эти оценки показывают, сколько времени и памяти требуется для выполнения алгоритма в зависимости от размера входных данных. 4

Для анализа сложности рекурсивных алгоритмов используют, например, метод подстановки, метод дерева рекурсии и метод мастера. 4