当前位置：首页 > news >正文

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

news 2025/6/7 12:01:26

递归解法

🔹第一步：定义本质问题

🔹第二步：分解问题结构

🔹第三步：定义初始条件

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

循环解法

🔹第 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→ 唯一直接能算出的总和

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

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

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

问题的结构性：每个总和是前一个总和加当前项；
最基本的事实：我们只知道 S(1)=1
由小推大的模式出现了，这就是递归的本质：

#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; // 状态变化
}

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

我们面对的问题具有重复性（相同操作、不同值）；
人为复制是不经济、脆弱的（写死 s = s + 1 + 2 + ... 会爆炸）；
我们想用一个“变化控制机制”让重复自动发生；
这就产生了循环语义：自动控制的重复结构。

公式解法

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

复杂度对比分析

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