您的递归代码具有指数运行时。但我不认为基数是2，但可能是黄金比例（约1.62）。但当然O（1.62 ^ n）也自动为O（2 ^ n）。

Your recursive code has exponential runtime. But I don't think the base is 2, but probably the golden ratio (about 1.62). But of course O(1.62^n) is automatically O(2^n) too.

运行时可以递归计算：

t(1)=1
t(2)=1
t(n)=t(n-1)+t(n-2)+1

这与斐波纳契数字本身的递归定义非常相似。递归方程中的 +1 可能与大n无关。 SI相信它的增长速度大约与fibo数一样快，并且随着黄金比率的增长呈指数增长。

This is very similar to the recursive definition of the fibonacci numbers themselves. The +1 in the recursive equation is probably irrelevant for large n. S I believe that it grows approximately as fast as the fibo numbers, and those grow exponentially with the golden ratio as base.

你可以使用memoization来加速它，即已经缓存计算结果。然后它就像迭代版本一样具有O（n）运行时。

You can speed it up using memoization, i.e. caching already calculated results. Then it has O(n) runtime just like the iterative version.

你的迭代代码的运行时间为O（n ）

Your iterative code has a runtime of O(n)

你有一个简单的循环，每次迭代都有O（n）步和恒定时间。

You have a simple loop with O(n) steps and constant time for each iteration.