咱们来一步步拆解这个问题，搞清楚你的递归斐波那契实现的复杂度到底符不符合预期～

先看你的代码逻辑 #

你用AtomicInteger统计的是每次进入fib方法的次数，也就是递归的总调用次数。实际运行这段代码的话，counter.intValue()最终会输出21891，而不是你预期的15127。这不是代码写错了，而是咱们得先区分清楚「渐近时间复杂度」和「实际调用次数」这两个概念。

为什么和φ²⁰的数值不一样？ #

你提到的φ^N（φ≈1.618，黄金比例）是递归斐波那契的渐近时间复杂度（用Θ(φⁿ)表示），它描述的是当n足够大时，算法运行时间的增长趋势，而不是精确的调用次数。

对于你的实现（定义F(0)=0，F(1)=1），计算F(n)的总调用次数有精确公式：

总调用次数 = 2 * F(n+1) - 1

这里的F(n)是第n个斐波那契数。代入n=20的话：

• F(21)的数值是10946
• 总调用次数 = 2*10946 - 1 = 21891

渐近复杂度和实际次数的关联 #

斐波那契数的通项公式是：

F(n) = (φⁿ - ψⁿ)/√5

其中ψ=(1-√5)/2≈-0.618，它的绝对值小于1，当n足够大时，ψⁿ会趋近于0，所以F(n)≈φⁿ/√5。

把这个近似代入总调用次数的公式：

总调用次数 ≈ 2*(φ^(n+1)/√5) = (2φ/√5)*φⁿ

计算一下系数：21.618/2.236≈1.447，所以总调用次数≈1.447φⁿ。对于n=20，φ²⁰≈15127，1.447*15127≈21890，和实际调用次数几乎完全一致。

结论 #

你的递归实现的时间复杂度完全符合Θ(φⁿ)的渐近预期——实际调用次数和φⁿ是同阶的，增长趋势完全匹配；只是精确数值因为通项公式里的低阶小项（ψⁿ）和常数系数的存在，和φⁿ有差异而已。

内容的提问来源于stack exchange，提问作者Maksym