B2.4.4–5 · HL 递归
递归求和
Python · 逐步执行
递归求和
观察调用如何逐层增加、到达基本情况，再按相反顺序返回。
Python 实现
1def recursive_sum(n):2 if n == 0:3 return 04 subtotal = recursive_sum(n - 1)5 return n + subtotalB2.4.5：简单的非分支递归函数。每次调用最多产生一次递归调用。对于非负的 n，时间复杂度为 O(n)，调用栈辅助空间为 O(n)。循环实现可使用 O(1) 辅助空间。