递归初步
函数调用自己，必须有出口，否则无限套娃导致栈溢出。
1. 完整例子
| 1 | int fact(int n) { |
| 2 | if (n <= 1) return 1; // 出口 |
| 3 | return n * fact(n - 1); |
| 4 | } |
| 5 | /* fact(5) = 5*4*3*2*1 = 120 */ |
2. 调用栈直觉
fact(5) 调用 fact(4)…直到 fact(1)，再一层层返回相乘。像叠盘子：压栈再弹栈。
3. 注意
- 先写出口再写递归式
- 深层递归占栈，嵌入式栈小要谨慎
- 很多递归可改写成循环