迭代与递归：从求和理解循环、终止条件与调用栈

同一个问题，两种控制结构

对非负整数 $n$，求 $S(n)=1+2+\cdots+n$，并约定 $S(0)=0$。迭代通过循环更新状态；递归通过函数调用把问题化为更小的同类问题，直到终止条件成立。原图的迭代与递归示意来自 Hello 算法，下文以可复制代码展开。

迭代：维护累加状态

def sum_iterative(n: int) -> int:
    if n < 0:
        raise ValueError("n must be non-negative")
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

每轮开始时，total 等于 $1+\cdots+(i-1)$；加入 i 后，它等于 $1+\cdots+i$。循环结束时已经加入 n，得到目标结果。这就是用循环不变式解释正确性。

递归：先缩小，再返回

$$S(n)=\begin{cases}0,&n=0,\\n+S(n-1),&n>0.\end{cases}$$

def sum_recursive(n: int) -> int:
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 0
    return n + sum_recursive(n - 1)

以 n=3 为例，调用先展开为 3 + (2 + (1 + S(0)))，到基线条件后返回 0，再逐层得到 1、3、6。每次递归都使非负整数 n 减小，因此最终到达 0；缺少基线或没有缩小问题，会导致无法正常结束。

复杂度与选择

实现	时间	额外空间	主要特点
循环求和	O(n)	O(1)	状态少，不增加递归深度
递归求和	O(n)	O(n)	表达递推关系，但保存调用栈

这里按基本算术操作计数，未计 Python 大整数随位数增长的开销。Python 不适合用很深的递归处理简单线性求和；树和分治问题则常适合先用递归表达结构。

对本例还可以两次反向求和：$S=(1+2+\cdots+n)$，$S=(n+(n-1)+\cdots+1)$，逐项相加得 $2S=n(n+1)$，所以 $S=n(n+1)/2$。控制结构只是实现手段，先找到更合适的数学关系可能更有效。