数据结构：递归：自然数之和

目录

递归解法

🔹第一步：定义本质问题

🔹第二步：分解问题结构

🔹第三步：定义初始条件

🔹第四步：递归思想的自然生成

循环解法

🔹第 1 步：定义问题最小操作单位

🔹第 2 步：识别模式：操作在变化，但结构不变

🔹第 3 步：构造“自我控制的重复流程”

公式解法 

复杂度对比分析

---

我们希望计算：

S(n)=1+2+3+⋯+n

我们运用第一性原理，从最基本的思考出发。

递归解法

🔹第一步：定义本质问题

我们的问题是：如何求“前 n 个自然数”的总和？

这是一个数学过程，它可以表示为：

S(n) = 1 + 2 + 3 + ⋯ + n

我们意识到这个总和的结果，和它前一项的总和非常接近。

例如：

• S(3) = 1+ 2 + 3 =6

• S(2) = 1 + 2 = 3

• 差值：3（恰好是第3项）

观察：

S(n) = S(n−1) + n

我们还没用“递归”这个词，但我们已经观察到了：

✅ 当前问题的解，等于一个更小规模的问题的解 + 当前项

🔹第二步：分解问题结构

我们从基本操作开始模拟：

• S(1)=1（这是我们唯一能确定的“基础真理”）

• S(2)=S(1)+2=1+2=3

• S(3)=S(2)+3=3+3=6

• S(4)=S(3)+4=6+4=10

于是我们归纳出结构性关系：

S(n)=S(n−1)+n

这时候，我们不是为了“递归编程”而发现这个关系，而是：

🔍我们通过“问题拆解”自然得出了一个问题依赖于更小版本的问题的解决结果的事实。

🔹第三步：定义初始条件

任何这种“问题拆解”机制，都需要一个，否则会无限拆解。

从实际观察：

S(1)=1→ 唯一直接能算出的总和

我们就可以从这里出发，逐步构建更大的答案。

🔹第四步：递归思想的自然生成

通过以上分析，我们从第一性原理推导出了：

1. 问题的结构性：每个总和是前一个总和加当前项；

2. 最基本的事实：我们只知道 S(1)=1

3. 由小推大的模式出现了，这就是递归的本质：

#include <iostream>int sumOfNumbers(int n)
{if (n == 0)return 0;elsereturn sumOfNumbers(n - 1) + n;
}

 

---

循环解法

🔹第 1 步：定义问题最小操作单位

最原始的求和操作，我们只能用 一个一个加起来 的方式。

例如：要计算 S(3)，你只能写：

int s = 0;
s = s + 1;
s = s + 2;
s = s + 3;

你会发现这段代码“重复”了完全相同的结构：

s = s + X;

只是每次 X 变了。

🔹第 2 步：识别模式：操作在变化，但结构不变

❗我们观察到：“结构一致，数值递增”的模式：

• 起始值从 1 到 n；

• 每次执行的指令是类似的；

• 只是某个变量（这里是 X）在以固定规律变化。

从第一性角度我们意识到：

✅ 为了避免重复写代码，我们应该“将重复的操作抽象为一个流程”，并让某些部分变化。

🔹第 3 步：构造“自我控制的重复流程”

我们定义：

• 一个当前项 i：表示我们正处理第几个数；

• 一个结束条件：当我们加到 n 时，停止；

• 一个变化规则：每次 i = i + 1。

于是我们就得到：

int s = 0;
int i = 1; // 初始状态while (i <= n) {s = s + i;i = i + 1; // 状态变化
}

从第一性原理看，“循环”之所以产生，是因为：

1. 我们面对的问题具有重复性（相同操作、不同值）；

2. 人为复制是不经济、脆弱的（写死 s = s + 1 + 2 + ... 会爆炸）；

3. 我们想用一个“变化控制机制”让重复自动发生；

4. 这就产生了循环语义：自动控制的重复结构。

公式解法 

int sumOfNumbers(int n)
{return n * (n + 1) / 2;
}

复杂度对比分析

方法	时间复杂度	空间复杂度	原因解释
✅递归	O(n)	O(n)	每次递归都需要函数调用栈，每次计算加法，总共调用 nn 次
✅循环	O(n)	O(1)	只需一个累加器和一个循环变量，占用常数空间
✅公式	O(1)	O(1)	只做一次乘法和一次除法，且不使用任何额外空间

⚠️注意事项

• 公式法虽然最快，但若 n 非常大（如 2^31 - 1），n*(n+1) 可能会产生整数溢出。可使用 long long 类型或进行乘法前除法优化。

• 递归法在 C++ 中若没有尾递归优化，容易栈溢出；在 Python 中栈深限制也较低。

• 循环法更通用、安全、稳定，适用于大多数工程需求。