递归求 1 到 n 的和

一句话算法

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

问题模型

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

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

核心直觉

设：

那么：

边界是：

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

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

算法步骤

普通递归

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

尾递归写法

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

定义 calc(a, n, s)：

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

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

算法证明

普通递归

用数学归纳法证明。

1. 当 n = 1 时，算法返回 1，正确。
2. 假设 sum_to_n(n-1) 能正确返回 1+2+...+(n-1)。
3. 则 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。

代码实现

普通递归

        
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;
}
    

尾递归

        
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;
}
    

测试用例

输入：

5

输出：

15

应用分类详解

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

一、线性递归

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

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

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

二、带累积参数的递归

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

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

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

经典例题

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

参考

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