【Python学习】递归算法
目录
5.2 减少栈溢出：尾递归优化（Python不支持，了解即可）
一、递归的核心概念
1.1 什么是递归？
递归（Recursion）是一种编程思想，指的是函数自身调用自身的编程方式。简单来说，就是一个函数在执行过程中，通过调用自己来解决规模更小的同类问题，直到遇到一个“终止条件”，停止递归并返回结果，最终组合出原问题的答案。
递归的本质是“分而治之”：将复杂问题拆解成与原问题结构一致、但规模更小的子问题，重复拆解直到子问题可直接解决（终止条件），再通过子问题的答案反向推导原问题的解。
举个生活中的例子：你想知道自己的族谱，问爸爸“你的爸爸是谁”（调用自身，规模缩小），爸爸再问爷爷，直到问到家族中第一个祖先（终止条件），然后从祖先开始，依次返回每个人的父亲，最终你就能得到自己的族谱——这就是递归的逻辑。
1.2 递归的两个核心要素（必记）
递归函数必须同时满足以下两个条件，否则会陷入无限循环（最终导致栈溢出），这是学习递归的关键：
-
终止条件（Base Case）：递归停止的条件，也是递归的“出口”。当问题规模缩小到满足这个条件时，函数不再调用自身，直接返回具体结果。
-
递归调用（Recursive Case）：函数自身调用自身，且每次调用时，问题的规模必须缩小（朝着终止条件靠近），不能重复相同规模的问题。
核心口诀：有出口，缩规模——缺少任何一个，递归都会失效。
二、Python递归函数的基本语法
2.1 语法结构
Python中递归函数的语法与普通函数一致，唯一的区别是函数体内包含对自身的调用，且必须先判断终止条件，再执行递归调用（避免无限循环）。
def 递归函数名(参数):
# 1. 终止条件（必须先写）
if 终止条件判断:
return 终止条件对应的结果
# 2. 递归调用（规模缩小）
else:
# 拆解子问题，调用自身
子问题结果 = 递归函数名(缩小后的参数)
# 3. 组合子问题结果，得到原问题结果（可选，根据需求）
return 组合后的结果2.2 最简单的递归示例：求1到n的和
需求：编写一个递归函数，计算1+2+3+...+n的和。
分析：
-
终止条件：当n=1时，和为1（最小规模的问题，可直接解决）。
-
递归调用：n的和 = n + (1到n-1的和)（将原问题拆解为“n”和“1到n-1的和”，规模缩小）。
def sum_recursion(n):
# 终止条件：n=1时，返回1
if n == 1:
return 1
# 递归调用：n + 前n-1个数的和（规模缩小）
else:
return n + sum_recursion(n - 1)
# 测试
print(sum_recursion(5)) # 输出：15（1+2+3+4+5）执行流程拆解（以n=5为例）：
sum_recursion(5) → 5 + sum_recursion(4)
sum_recursion(4) → 4 + sum_recursion(3)
sum_recursion(3) → 3 + sum_recursion(2)
sum_recursion(2) → 2 + sum_recursion(1)
sum_recursion(1) → 1（终止条件）
反向计算：1 → 2+1=3 → 3+3=6 → 4+6=10 → 5+10=15，最终返回15。
三、Python递归的经典实例（必练）
以下实例覆盖递归的常见应用场景，从基础到进阶，帮助你理解递归的核心逻辑，建议逐行拆解代码、手动模拟执行流程。
实例1：阶乘计算（基础）
阶乘定义：n! = n × (n-1) × (n-2) × ... × 1，且0! = 1，1! = 1。
分析：
-
终止条件：n=0或n=1时，返回1。
-
递归调用：n! = n × (n-1)!（规模缩小为n-1）。
def factorial(n):
# 终止条件：n=0或n=1，返回1
if n in (0, 1):
return 1
# 递归调用：n × (n-1)!
else:
return n * factorial(n - 1)
# 测试
print(factorial(5)) # 输出：120（5×4×3×2×1）
print(factorial(0)) # 输出：1（符合阶乘定义）实例2：斐波那契数列（进阶）
斐波那契数列定义：从第3项开始，每一项都等于前两项之和，即：1, 1, 2, 3, 5, 8, 13, ...
需求：编写递归函数，求第n项斐波那契数（n≥1）。
分析：
-
终止条件：n=1或n=2时，返回1（前两项固定为1）。
-
递归调用：第n项 = 第(n-1)项 + 第(n-2)项（规模缩小为n-1和n-2）。
def fibonacci(n):
# 终止条件：n=1或n=2，返回1
if n == 1 or n == 2:
return 1
# 递归调用：第n项 = 第n-1项 + 第n-2项
else:
return fibonacci(n - 1) + fibonacci(n - 2)
# 测试
print(fibonacci(5)) # 输出：5（第5项：1,1,2,3,5）
print(fibonacci(7)) # 输出：13（第7项）注意：该递归实现存在重复计算（比如计算fibonacci(5)时，会重复计算fibonacci(3)、fibonacci(2)等），效率较低。后续会讲解优化方法。
实例3：反转字符串（应用）
需求：编写递归函数，将字符串反转（如输入"abcde"，输出"edcba"）。
分析：
-
终止条件：字符串长度为0或1时，直接返回原字符串（无法再缩小规模）。
-
递归调用：反转字符串 = 最后一个字符 + 反转（除最后一个字符外的子串）（规模缩小为原字符串长度-1）。
def reverse_str(s):
# 终止条件：字符串长度≤1，返回自身
if len(s) ≤ 1:
return s
# 递归调用：最后一个字符 + 反转剩余子串
else:
return s[-1] + reverse_str(s[:-1])
# 测试
print(reverse_str("abcde")) # 输出：edcba
print(reverse_str("python")) # 输出：nohtyp实例4：遍历目录（实战）
需求：使用递归遍历指定目录下的所有文件（包括子目录中的文件）。
分析：
-
终止条件：当前路径是文件时，直接打印文件路径（无法再拆解）。
-
递归调用：当前路径是目录时，遍历目录下的所有子项，对每个子项再次调用自身（规模缩小为子目录/文件）。
import os
def traverse_dir(path):
# 遍历当前路径下的所有子项（文件/目录）
for item in os.listdir(path):
# 拼接完整路径
full_path = os.path.join(path, item)
# 终止条件：如果是文件，打印路径
if os.path.isfile(full_path):
print("文件：", full_path)
# 递归调用：如果是目录，继续遍历子目录
else:
print("目录：", full_path)
traverse_dir(full_path)
# 测试（替换为自己的目录路径）
traverse_dir("D:/test")说明：该实例结合了Python的os模块，是递归在文件操作中的典型应用，实际开发中非常常用。
四、递归的执行原理（栈机制）
Python中递归的执行依赖于“调用栈”（Call Stack），理解栈机制能帮助你避免递归错误，核心逻辑如下：
-
当函数调用自身时，Python会将当前函数的执行状态（参数、局部变量、执行位置）压入调用栈，然后执行新的递归调用。
-
当递归达到终止条件时，函数会返回结果，此时Python会从调用栈中弹出最顶层的函数状态，继续执行上一层函数的剩余代码。
-
重复步骤2，直到所有函数状态弹出栈，最终返回原问题的结果。
调用栈的容量是有限的——Python默认的递归深度（栈的最大层数）约为1000。如果递归深度超过这个限制，会抛出RecursionError（递归错误）。
# 测试递归深度限制
def test_depth(n):
if n == 0:
return
test_depth(n - 1)
test_depth(1000) # 正常执行（接近默认深度）
test_depth(1001) # 抛出RecursionError: maximum recursion depth exceeded五、递归的优化技巧
递归的优点是代码简洁、逻辑清晰，但缺点是可能存在重复计算、栈溢出等问题，以下是常用的优化方法：
5.1 避免重复计算：记忆化缓存（Memoization）
针对斐波那契数列这类存在大量重复计算的场景，可使用“记忆化缓存”——将已经计算过的子问题结果存储起来，下次需要时直接调用，无需重复计算。
Python中可使用lru_cache装饰器（从functools导入）快速实现缓存：
from functools import lru_cache
# 装饰器实现记忆化缓存，缓存已计算的结果
@lru_cache(maxsize=None) # maxsize=None表示无限制缓存
def fibonacci_optimized(n):
if n == 1 or n == 2:
return 1
else:
return fibonacci_optimized(n - 1) + fibonacci_optimized(n - 2)
# 测试：效率大幅提升，可计算更大的n
print(fibonacci_optimized(100)) # 快速输出结果，无重复计算5.2 减少栈溢出：尾递归优化（Python不支持，了解即可）
尾递归：指递归调用是函数的最后一步操作（没有后续的计算），此时调用栈可以被优化，无需保存上一层函数的状态，从而减少栈溢出的风险。
注意：Python官方解释器（CPython）不支持尾递归优化，即使写了尾递归代码，依然会占用调用栈，该知识点仅作了解，后续可学习其他语言（如Scala、Scheme）的尾递归实现。
# 尾递归版本的斐波那契（Python中依然会栈溢出，仅作示例）
def fibonacci_tail(n, a=1, b=1):
if n == 1 or n == 2:
return b
# 递归调用是最后一步，无后续计算（尾递归）
return fibonacci_tail(n - 1, b, a + b)
print(fibonacci_tail(1000)) # 依然抛出RecursionError5.3 替代方案：递归转迭代
对于递归深度较大的场景，可将递归逻辑改为迭代（循环），完全避免栈溢出问题，虽然代码逻辑不如递归简洁，但效率更高、更稳定。
示例：将斐波那契数列的递归实现改为迭代实现：
def fibonacci_iterative(n):
if n == 1 or n == 2:
return 1
# 迭代：用变量保存前两项的值，避免重复计算
a, b = 1, 1
for _ in range(3, n + 1):
a, b = b, a + b # 每次更新前两项
return b
print(fibonacci_iterative(1000)) # 正常执行，无栈溢出六、递归的适用场景与注意事项
6.1 适用场景
递归并非万能，以下场景更适合使用递归：
-
问题可拆解为“同类子问题”，且子问题规模更小（如阶乘、斐波那契）。
-
场景本身具有递归特性（如目录遍历、树的遍历、回溯算法）。
-
代码简洁性优先于效率（递归代码通常比迭代更短）。
6.2 注意事项（必避坑）
-
必须有明确的终止条件：否则会陷入无限递归，最终抛出RecursionError。
-
确保递归调用时规模缩小：比如n→n-1，而不是n→n或n→n+1，否则无法到达终止条件。
-
避免重复计算：对于重复计算严重的场景，使用记忆化缓存或迭代优化。
-
控制递归深度：Python默认递归深度有限，超过1000需考虑迭代或手动修改递归深度（不推荐）。
# 不推荐：手动修改递归深度（可能导致内存溢出）
import sys
sys.setrecursionlimit(2000) # 将递归深度改为2000
test_depth(1500) # 此时可正常执行七、练习题目（巩固提升）
以下练习从易到难，建议独立完成，巩固递归的核心逻辑：
-
编写递归函数，求两个正整数的最大公约数（GCD），提示：使用辗转相除法（gcd(a,b) = gcd(b, a%b)，终止条件：b=0时返回a）。
-
编写递归函数，计算1到n的乘积（即阶乘的变种，与实例1呼应）。
-
编写递归函数，判断一个字符串是否是回文（如"abba"是回文，"abc"不是回文）。
-
进阶：使用递归实现快速排序（Quick Sort），核心逻辑：选择一个基准值，将数组分为“小于基准”和“大于基准”两部分，分别递归排序，最后合并。
练习提示：遇到困难时，先拆解问题、确定终止条件，再编写递归调用，手动模拟小规模输入的执行流程，逐步调试。
八、总结
递归是Python中重要的编程思想，核心是“分而治之”，关键在于把握“终止条件”和“递归调用”两个要素。
学习递归的重点的是：理解执行流程、拆解问题、避免坑点。初期可通过手动模拟执行流程（如阶乘、斐波那契），熟悉递归的逻辑；后期可结合缓存、迭代等优化方法，解决实际开发中的问题。
记住：递归不是目的，而是一种工具——当它能让代码更简洁、逻辑更清晰时使用，当它导致效率低下或栈溢出时，可考虑迭代等替代方案。
这里是“一人公司”的成长家园。我们提供从产品曝光、技术变现到法律财税的全栈内容，并连接云服务、办公空间等稀缺资源，助你专注创造，无忧运营。
更多推荐
14
0- 0
已为社区贡献14条内容
所有评论(0)