让我们想象一下对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）。
