递归算法python版

递归算法是一种函数调用自身来解决问题的方法。其核心思想是“将大问题分解为小问题”，直到遇到最基本的情况（也叫“基线条件”），再逐步回溯解决整个问题。

【递归基本结构】

一个递归函数一般包括两个部分：

1. 基线条件（终止条件）：避免无限递归，定义什么时候停止。

2. 递归调用：函数调用自身，解决规模更小的子问题。

【示例题目：1加到10】

目标是计算 1 + 2 + 3 + ... + 10 的和。

可以将这个问题看作：

sum(10) = 10 + sum(9)
sum(9)  = 9  + sum(8)
...
sum(2)  = 2  + sum(1)
sum(1)  = 1  // 到这里为止，不再递归

【递归代码示例（Python）】

def recursive_sum(n):
    if n == 1:  # 基线条件
        return 1
    else:
        return n + recursive_sum(n - 1)

调用 recursive_sum(10)，结果就是 55。

【递归调用过程可视化】

recursive_sum(10)
= 10 + recursive_sum(9)
= 10 + 9 + recursive_sum(8)
= 10 + 9 + 8 + recursive_sum(7)
...
= 10 + 9 + 8 + ... + 1
= 55

递归调用会一直“向下”直到到达基线条件（n == 1），然后从 1 开始“向上”返回并逐步累加。

【注意事项】

1. 必须设置终止条件，否则会造成无限递归，导致栈溢出。

2. 每一次函数调用都会占用内存，因此递归效率一般不如循环。

3. 适合用于：

• 分治问题（如归并排序、快速排序）

• 树形结构遍历（如二叉树）

• 数学问题（如斐波那契数列、阶乘）

【等效的循环写法】

def loop_sum(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

这段代码与递归版本功能一样，但效率更高，不占用调用栈空间。

要完整描述从 recursive_sum(10) 递归调用到回溯的全过程，下面从递归调用和回溯返回两个阶段，逐步展开：

一、递归阶段（调用阶段）

这是从 n=10 不断调用自身，直到满足终止条件 n == 1：

recursive_sum(10)
→ 10 + recursive_sum(9)
→ 10 + 9 + recursive_sum(8)
→ 10 + 9 + 8 + recursive_sum(7)
→ 10 + 9 + 8 + 7 + recursive_sum(6)
→ 10 + 9 + 8 + 7 + 6 + recursive_sum(5)
→ 10 + 9 + 8 + 7 + 6 + 5 + recursive_sum(4)
→ 10 + 9 + 8 + 7 + 6 + 5 + 4 + recursive_sum(3)
→ 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + recursive_sum(2)
→ 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + recursive_sum(1)

此时遇到基线条件：

recursive_sum(1) = 1   // 停止递归，开始回溯

二、回溯阶段（逐层返回）

从 recursive_sum(1) 返回，依次把结果带回到上一个函数调用中：

recursive_sum(1) = 1
→ 返回给 recursive_sum(2) → 2 + 1 = 3
→ 返回给 recursive_sum(3) → 3 + 3 = 6
→ 返回给 recursive_sum(4) → 4 + 6 = 10
→ 返回给 recursive_sum(5) → 5 + 10 = 15
→ 返回给 recursive_sum(6) → 6 + 15 = 21
→ 返回给 recursive_sum(7) → 7 + 21 = 28
→ 返回给 recursive_sum(8) → 8 + 28 = 36
→ 返回给 recursive_sum(9) → 9 + 36 = 45
→ 返回给 recursive_sum(10) → 10 + 45 = 55

最终结果是 55

三、完整调用和回溯堆栈视图（栈的形式）

每次调用会进入“调用栈”中，最后一个最先返回：

调用栈入栈过程：

recursive_sum(10)
→ recursive_sum(9)
→ recursive_sum(8)
→ ...
→ recursive_sum(1)  // 到此为止

出栈过程：

recursive_sum(1) 返回 1
→ recursive_sum(2) 返回 2 + 1 = 3
→ recursive_sum(3) 返回 3 + 3 = 6
→ ...
→ recursive_sum(10) 返回 10 + 45 = 55

四、关键点总结

• 每一层函数都等待下一层的返回结果；

• 返回时，按调用的反顺序向上层回溯计算；

• 每个返回值是当前数字加上下一层返回值；

• 最终汇总成完整的结果。