递归

递归对于初学者来说是一个非常头疼的概念。如果你觉得暂时无法理解，请不要灰心，因为正常的人类倾向于使用递推思考问题，即从一个 base case 出发从小往大推，而不是把一个大的问题逐渐拆解。但你必须逐渐习惯计算机世界中的这种将大任务拆成小任务解决的思想，大家后面会接触到的分治思想更是将这一点发挥到了极致。

这篇讲义希望用一个故事把递归的思想讲明白。假设一个国家的国王有一个任务：计算 $1+2+\cdots+100$。日理万机的国王肯定不会一个一个累加浪费时间，但他也没有聪明到能够发现高斯公式。幸运的是他有一批听话的大臣可以使用，于是他设计了一个这样的策略：

让丞相去计算 $1+2+\cdots +99$，等他把结果返回给我了，我只要计算这个结果+100，答案就出来了。

丞相同样忙碌且数学天分不高，但幸运的是他也有一批手下可以召唤，于是他设计了一个同样的策略：

找一个手下大臣去计算 $1+2+\cdots +98$，等他把结果返回给我了，我只要计算这个结果+99，就能向国王交差了。

这个王国的所有人都深谙资本主义压榨下属的套路 (bushi)，于是这个任务被一级一级传递下去，直到村长拿到 $1+2+3$ 时，把 $1+2$ 这个任务分配给了一个普通的村民。村民没有手下可以使用了，但幸运的是这个问题足够简单，他想都没想就机智地得到了答案 $3$ 并将结果返回给了村长。村长收到 $3$ 后计算出 $3+3=6$，又将结果返回给了镇长……一路下放的任务在收结果的过程中又被一路上传回去，最后国王收到了丞相的回复：$4950$，于是他完成了最后一步加法，$4950+100=5050$，并很高兴地宣称该任务圆满结束。

这样的写法可能还不足以唤醒你在课堂上学习的递归“套路”。我们不妨写的更形式化一点：令 $F(n)$ 表示计算 $1+2+\cdots +n$ 这个任务，那么国王的任务是计算 $F(100)$，丞相的任务是计算 $F(99)$……镇长的任务是计算 $F(4)$，村长的任务是计算 $F(3)$。不论这个参数是大是小，他们都采取了相同的战术： $$ F(n)=F(n-1)+n $$ 只有村民不一样，他的任务就是一个简单的加法。所以整个王国的策略可以被归纳为 $$ F(n)= \begin{cases} 3&,n=2\\ F(n-1)+n&,n\geq 3 \end{cases} $$ 这就是递归的基本思想：如果一个大任务 (例如 $F(n)$) 可以被分解成一个性质相同但规模更小的任务 (例如 $F(n-1)$) 以及一些简单的额外运算 (例如 $+n$)，那么这个问题就非常适合用递归解决。我们可以为上面的递归加法写一个程序：

int query_sum(int n)
{
    if (n == 2)
        return 3;
    else
        return query_sum(n - 1) + n;
}

该函数的执行过程和王国里任务下放再回收的过程完全相同：query_sum(100) 调用 query_sum(99) 等待其返回值，query_sum(99) 又调用了 query_sum(98)……从而形成了一个长长的调用链。query_sum(3) 调用 query_sum(2) 时，query_sum(2) 不需要再调用子函数，直接返回了结果，从而 query_sum(3) 执行完加法后也返回了结果，一层层返回结果，直到 query_sum(100) 返回。

大家更加喜闻乐见的可能是小学/中学接触过的斐波那契数列： $$ fib_n= \begin{cases} 0&, n=0\\ 1&, n=1\\ fib_{n-1}+fib_{n-2}&, n\geq 2 \end{cases} $$

能够写出这种递推式的数列一定可以非常简明地用递归实现计算：

int query_fib(int n)
{
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return query_fib(n - 1) + query_fib(n - 2);
}

这个例子比上一个例子稍稍复杂一些，因为它把一个大任务分解成了两个小任务，可以想象递归的调用会形成一个树状结构而不是链状结构。你可以自己用纸笔画一画 query_fib(5) 的递归调用过程，画完之后参考 这个链接 的动画进行比对。