递归
递归，是指一个函数通过在「同一个问题的更小版本」上调用自己来求解。脑海里可以想象一组俄罗斯套娃：要打开最大的娃娃，就得打开里面那个稍小一点的，而它里面又套着更小的，直到最小那个一打开里面什么也没有。那个最小的娃娃正是关键所在——每一段正确的递归都有一个基准情形（base case），即简单到无需再调用就能直接给出答案的情况；以及一个递归情形，它做一点点工作，再把剩下的交给更小的一次调用。「4 的阶乘是多少？」变成「4 乘以 3 的阶乘」，再变成「4 乘 3 乘 2 的阶乘」，如此一路降到 0 的阶乘——我们直接规定它等于 1。
从机制上看，每一次调用都有自己的小工作区——它自己的那一份局部变量——一层层叠放在前一次调用之上，存放在内存中一块叫做调用栈（call stack）的区域。计算机一路向下俯冲，堆起一串未完成的调用，直到撞上基准情形；接着开始回卷，沿途逐一完成每一个挂起的调用，把答案交还给正在等待它的那一层。如果你忘了写基准情形（或者根本没有朝它靠近），栈就会不断增长，直到程序以栈溢出（stack overflow）崩溃——这正是递归最出名的失败方式。
递归是一种思维方式，并非免费的午餐。朴素的递归可能把同一个子问题反反复复地重算：用最直白的两路递归去算第 n 个斐波那契数会指数级分叉，本该只需 O(n) 的事情却做了大约 O(2^n) 的工作。补救之道，要么记住已经算过的答案（记忆化 memoization），要么把递归翻转成一个自底向上填表的循环（动态规划 dynamic programming）。递归也是分治法以及遍历树、图结构最自然的表达语言。
int fib(int n) {
if (n < 2) return n; // base case
return fib(n - 1) + fib(n - 2); // recursive case (branches!)
}
// fib(4)
// / \
// fib(3) fib(2)
// / \ / \
// fib(2) fib(1) fib(1) fib(0)
// / \
// fib(1) fib(0)同一个子问题出现在多个分支上——这正是记忆化要消除的浪费。
原则上，每一段递归都能用一个显式的栈改写成循环，反之亦然。某些语言会优化一种特例——尾递归，即递归调用是函数做的最后一件事——把它变成不耗费额外栈空间的普通循环；C++ 编译器可能这样做，但并不保证，所以别指望靠它来支撑无限深度。