Какова глубина следующей рекурсивной функции?
T(n) = r + T(n-r)
, где r < n и если 2r > n, то r = n-r, и условие остановки, если n = r
Пример:
n = 24, r = 9
2r < n, 2*9 < 24, r is fixed (r=9)
T(24) = 9 + T(24-9)= 9 + T(15)
----------
2r > n, 2*9 >15, then r = 15 - 9 = 6
T(15) = 6 + T(15-6)= 6 + T(9)
------------
2r > n, 2*6 > 9, r = 9- 6 = 3
T(9) = 3 + T(9-3) = 3 + T(6)
-----------
2r = n, 2*3 = 6, r is fixed (r=3)
T(6) = 3 + T(6- 3) = 3 + T(3)
------------
Stop condition, r equals n
Сложность по времени O (n).
Эта проблема может быть решена с помощью деревьев рекурсии, но это решение не является общим для всех значений n и r.
Я ищу формулу, чтобы найти глубину этого рекурсивного уравнения.