递归函数

自己调用自己

函数在执行时调用自己，这种写法叫作递归。

每次把问题缩小，遇到能直接给出答案的情况，就返回。这种情况叫作边界。

求 1 到 n 的和

f(n) 表示 1 到 n 的和。前 n-1 个数的和，再加 n，就是答案。

f(n) = f(n - 1) + n
f(1) = 1

这里处理 1 <= n <= 1000。

#include <iostream>

using namespace std;

int f(int n) {
    if (n == 1) return 1; // 边界，直接给出答案

    return f(n - 1) + n;
}

int main() {
    int n;
    cin >> n;

    cout << f(n);

    return 0;
}

观察执行过程

以 f(3) 为例，先往下调用，再往回计算。

调用：一直找到边界。

f(3) 等待 f(2) 的结果
f(2) 等待 f(1) 的结果
f(1) 到达边界，返回1

返回：一层一层算出结果。

f(2) 得到1，再加2，返回3
f(3) 得到3，再加3，返回6

每次调用，都有自己的 n。 f(3) 等待时，它的 n 还是 3；f(2) 返回后，它再加 3。

再看图中的 f(5)，自己跟着走一遍。

写递归，先想三件事

函数表示什么？

本例中，f(n) 表示 1 到 n 的和。

问题的边界

本例中，n == 1 时，直接返回 1。

求解子问题

调用 f(n - 1)，把结果加上 n。参数每次减 1，逐渐靠近边界。

常见错误

没有边界，或者走不到边界。

return f(n) + n; // 错误：参数没变，走不到边界

本例应调用 f(n - 1)。输入也要符合范围；输入 0，会不断减到 -1、-2……，碰不到 1。

递归调用，不等于返回结果。

f(n - 1) + n; // 错误：计算了表达式，却没有把结果返回

应该写 return f(n - 1) + n;。

调用层数太多，程序也可能出错。 不能只看计算结果会不会超范围。

这道求和题，用循环也能做。这里是借它认识递归的执行过程。