（七）递归调用与返回顺序

统计一个嵌套分组的时长时，一个分组内部还可能包含分组。先用更小的任务观察函数调用自身：计算 1 + 2 + ... + n，本例输入一个非负整数。

# total_to(n) 把当前 n 留下，先取得 total_to(n - 1) 的结果。
def total_to(n):
    if n == 0:
        return 0
    smaller = total_to(n - 1)
    return n + smaller


print(total_to(3))

输出 6。先后进入 total_to(3)、total_to(2)、total_to(1)、total_to(0)；前三次都停在等待 smaller 的位置。最内层返回 0 后，依次完成 1 + 0、2 + 1、3 + 3。

每次尚未返回的调用都要保存自己的局部状态与继续位置，这些调用组成调用栈。这个程序有 $O(n)$ 次调用，同时保存 $O(n)$ 层状态；改成循环累加只需几个状态变量。Python 的深层递归会触及解释器递归深度限制并报告 RecursionError，长串线性处理可以直接写循环；后面处理树形数据时，再按分支结构组织递归。

阅读递归时，分开看两个方向：进入时把什么交给更小的一次调用，返回时把拿回的结果怎样继续加工。只看最后一行相加，容易遗漏中间等待的调用。