01先读懂这个概念
先给函数一个清楚的承诺
定义 triangular(n) 返回 1+2+…+n，输入要求 n 是非负整数。对于 n=4，答案可以写成 4+triangular(3)。当前层负责加上 4，较小的调用负责 1 到 3；这是一份分工，而不是一句『相信递归』。
分工必须能结束。n=0 时答案是 0，不再调用自己。对于 n>0，每次传入 n−1，最终一定到达 0。若每次仍调用 triangular(n)，问题没有变小，就会无限递归直到调用栈溢出。
调用栈保存了被暂停的计算
triangular(4) 遇到 triangular(3) 时，暂时无法完成加法，于是保存『等它返回后加 4』。下一层保存『加 3』，再下一层保存『加 2』。这些等待中的任务后进先出，正好由上一章的栈表示。
每次调用的 n 是各自的局部变量，进入 n=3 不会把外层的 n=4 覆盖。返回时先完成最内层，再把结果交给它的调用者。下面的递归只有一条调用链，没有重复子问题；到动态规划课再看分叉的调用树。
02从具体数据开始手算
拿一个小输入，逐步手算
计算 triangular(4)。
| 方向 | 当前调用 | 暂停或返回的工作 |
|---|---|---|
| 展开 | T(4) | 等待 T(3)，返回后加 4 |
| 展开 | T(3) | 等待 T(2)，返回后加 3 |
| 展开 | T(2) | 等待 T(1)，返回后加 2 |
| 展开 | T(1) | 等待 T(0)，返回后加 1 |
| 终止 | T(0)=0 | 直接返回 0 |
| 返回 | T(1)=1，T(2)=3 | 逐层完成加法 |
| 返回 | T(3)=6，T(4)=10 | 最外层得到 10 |
展开过程还没有完成那些加法；答案沿调用栈向上返回。写递归时必须同时想清『传下去什么』和『返回后做什么』。
03把正确性的理由说清楚
用小规模正确性支撑大规模
- 基础情形：T(0)=0，确实等于空和。
- 假设 T(n−1) 正确返回 1 到 n−1 的和，加上 n 就是 1 到 n 的和，因此当前层正确。
- 非负整数 n 每次严格减一，必定到达基础情形，所以这种递推不只是形式上正确，也会终止。
04把刚才的思路写成代码
基础课用 Python 表达，先对照变量含义与执行顺序。后续算法课提供 Python、C++ 与 JavaScript 三种实现。
def triangular(n):
if n < 0:
raise ValueError('n must be non-negative')
if n == 0:
return 0
return n + triangular(n - 1)代码里的每个关键决定
if n == 0:- 这是可以不依赖其他调用而直接回答的基础情形。它不是随意添加的防报错语句。
return n + triangular(n - 1)- 当前 n 保留在当前栈帧里；等子调用返回后再做加法。这里不是尾递归，因为返回后还有加法。
triangular(n - 1)- 参数严格变小。输入约定为非负整数；负数必须拒绝，否则不断减一永远到不了 0。
05这些操作要付出多少代价
把工作量具体数出来
共有 n+1 次调用（包含 n=0），每层做常数次工作，因此按定长运算模型计时间 O(n)。
最深时有 n+1 个尚未返回的栈帧，辅助空间 O(n)。不能因为代码里没有创建数组，就写成 O(1)。
Python 有递归深度限制，这个教学函数只适合小 n。求这个具体和更适合循环或公式；我们用它练习调用机制，不把递归视为所有问题的首选。
06用一个反例检查理解
有基础情形，也可能永远到不了
函数写了 if n==0，却在 n>0 时递归调用自身的 n，而不是 n−1。以 4 开始，参数一直是 4，基础情形永远不会触发。
怎样修正：每次检查一个能保证进展的量，比如区间长度、未处理元素个数或树高；不仅要有停止条件，还要证明能走到它。
07自己推一次，再做自测
把递归改成循环
手算 triangular(3) 的返回过程，再写出用 result=0 和一个循环完成相同计算的思路。两个版本的辅助空间有什么不同？
需要一点提示
递归保存待执行的加法；循环可以立即把加法累积进 result。
查看完整推导与答案
- T(0)=0 → T(1)=1 → T(2)=3 → T(3)=6。
- 循环 i=1..3，依次执行 result+=i，累计得到 1、3、6。
- 时间都是 O(n)，循环只保留计数器与累计值，为 O(1) 辅助空间；递归栈为 O(n)。