我的算法书 - 递归求 1 到 n 的和

一句话算法

递归求和把 1+2+...+n 拆成 n + (1+2+...+(n-1))。

问题模型

输入一个正整数 n，计算：

1+2+\cdots+n

虽然这道题可以直接用公式 $\frac{n(n+1)}{2}$ ，但它很适合用来理解递归如何把大问题拆成小问题。

核心直觉

设：

f(n)=1+2+\cdots+n

那么：

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

边界是：

f(1)=1

这就是递归最基本的两部分：

递归式：如何把当前问题拆成更小问题。
边界：小到什么时候可以直接回答。

算法步骤

普通递归

如果 n == 1，返回 1。
否则返回 n + sum_to_n(n - 1)。

尾递归写法

也可以把“已经算出的和”放进参数里。

定义 calc(a, n, s)：

已经累加了 1..a-1。
当前和是 s。
接下来处理 a。

如果 a == n + 1，说明 1..n 已经全部处理完，返回 s。

算法证明

普通递归

用数学归纳法证明。

当 n = 1 时，算法返回 1，正确。
假设 sum_to_n(n-1) 能正确返回 1+2+...+(n-1)。
则 n + sum_to_n(n-1) 等于 1+2+...+n。

所以算法对所有正整数 n 正确。

尾递归

关键不变量： 进入 calc(a, n, s) 时，s = 1+2+...+(a-1)。

初始 calc(1, n, 0) 满足空和为 0。每次递归进入 calc(a+1, n, s+a)，新的 s 正好变成 1+...+a。当 a = n+1 时，s = 1+...+n，返回正确答案。

复杂度分析

时间复杂度： $O(n)$ 。
空间复杂度： $O(n)$ ，递归调用栈深度为 n。

代码实现

普通递归

C++

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

        #include <bits/stdc++.h>
using namespace std;

// f(n) 表示 1 + 2 + ... + n。
int sum_to_n(int n) {
    if (n == 1) return 1;
    return n + sum_to_n(n - 1);
}

int main() {
    int n;
    cin >> n;
    cout << sum_to_n(n) << '\n';
    return 0;
}

Python

python

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

        # 递归求 1 + 2 + ... + n，f(n) = n + f(n-1)，f(1) = 1。
# 递归深度为 n，n 较大时 main 中已抬高 sys.setrecursionlimit。
# n < 1 会无限递归（与 C++ 一样越界），输入保证 n >= 1。
# 结果可能超过 32 位，Python int 任意精度，无 C++ 的 int 溢出问题。
import sys


def sum_to_n(n: int) -> int:
    if n == 1:
        return 1
    return n + sum_to_n(n - 1)


def main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    sys.setrecursionlimit(max(1000, n + 100))
    print(sum_to_n(n))


if __name__ == "__main__":
    main()

尾递归

C++

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

        #include <bits/stdc++.h>
using namespace std;

// calc(a, s): 已经累加到 a - 1，当前和是 s，接下来处理 a。
int calc(int a, int n, int s) {
    if (a == n + 1) return s;
    return calc(a + 1, n, s + a);
}

int main() {
    int n;
    cin >> n;
    cout << calc(1, n, 0) << '\n';
    return 0;
}

Python

python

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

        # 尾递归求 1 + 2 + ... + n：calc(a, s) 表示已累加到 a-1、当前和为 s。
# 终止条件 a == n + 1 返回 s，对应 C++ 的 calc(1, n, 0)。
# 递归深度为 n + 1，n 较大时 main 中已抬高 sys.setrecursionlimit。
# Python 不做尾调用优化，深度仍是 O(n)；结果任意精度，无 int 溢出问题。
import sys


def calc(a: int, n: int, s: int) -> int:
    if a == n + 1:
        return s
    return calc(a + 1, n, s + a)


def main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    sys.setrecursionlimit(max(1000, n + 100))
    print(calc(1, n, 0))


if __name__ == "__main__":
    main()

测试用例

输入：

输出：

应用分类详解

递归求和的本质是“当前项 + 更小规模答案”。

一、线性递归

典型模式： f(n) 只依赖一个更小的 f(n-1)。

识别信号： 前 n 项、前缀结果、逐个处理。

核心建模： 当前层处理第 n 个对象，剩下交给 n-1。

二、带累积参数的递归

典型模式： 递归过程中需要维护一个已经处理好的部分结果。

识别信号： 当前和、当前乘积、当前路径、当前状态。

核心建模： 把累积值作为递归参数传给下一层。

经典例题

递归求阶乘：fac(n)=n*fac(n-1)。
递归求数组前缀和：当前元素加剩余部分。
链表递归处理：当前节点加后续链表结果。

参考

本书相关章节：递归的前进与回溯