一句话理解
递归调用过程可以想成一叠等待中的任务。
为什么要学
会画调用树，才知道它算了几次、会不会重复。
讲解
每次调用都暂停当前函数，进入更小的问题，等结果回来再继续。
Fibonacci 朴素递归会把同样的 f(k) 算很多遍。这就是后面要记忆化的原因。
例子
f(3)
├─ f(2)
│ ├─ f(1)
│ └─ f(0)
└─ f(1)f(3) 先等 f(2) 和 f(1)。f(2) 再等 f(1) 和 f(0)。同一 f(1) 出现两次。
常见错误
- 以为递归是循环的语法糖，忽略重复计算。
- 不在纸上画就难查错。