f (int n){ if (n<=0){ return 1; } return f(n-1) + f(n-1); }
假设我们做了f（4）。我的想法是它将是O（2 ^ n），此后为了找到f（n-1）+ f（n-1），我们必须将f（n-1）= f（3）推到调用堆栈两次，然后f（2）调用堆栈的四倍，依此类推。但是，我从这本书中得到的书说是O（n）。为什么会这样呢？
让我们想象一下对f（4）进行评估（您考虑的示例）。这是怎么回事。堆栈从看起来像
I need to compute f(4)
然后f（4）的计算返回到f（3），堆栈看起来像
I need to compute f(4), so I need to compute f(3)
然后我们继续下降，最终到达
I need to compute f(4), so I need to compute f(3), so I need to compute f(2), so I need to compute f(1), so I need to compute f(0)
然后，我们可以将f（0）计算为1，最后一次调用返回。倒数第二个调用（用于计算f（1）的那个），然后要计算f（0）的第二个副本，堆栈将转到：
I need to compute f(4), so I need to compute f(3), so I need to compute f(2), so I need to compute f(1), and although I've already computed the first f(0)=1, I still need to compute the second occurrence of f(0), so I need to compute f(0) (again)
然后返回，因此f（1）的计算可以返回，我们得到
I need to compute f(4), so I need to compute f(3), so I need to compute f(2), and although I've already computed the first f(1)=2, I still need to compute the second occurrence of f(0)
从那里堆栈变成：
I need to compute f(4), so I need to compute f(3), so I need to compute f(2), and although I've already computed the first f(1)=2, I still need to compute the second occurrence of f(0), so... I need to compute f(1)
它将继续像以前一样计算f（1）。
关键是，即使（最终）将执行2 ^ n次运算，堆栈也只能达到n的深度。因此，时间复杂度为O（2 ^ n），但空间复杂度仅为O（n）。
