【Python学习】递归算法

目录一、递归的核心概念1.1 什么是递归1.2 递归的两个核心要素必记二、Python递归函数的基本语法2.1 语法结构2.2 最简单的递归示例求1到n的和三、Python递归的经典实例必练实例1阶乘计算基础实例2斐波那契数列进阶实例3反转字符串应用实例4遍历目录实战四、递归的执行原理栈机制五、递归的优化技巧5.1 避免重复计算记忆化缓存Memoization5.2 减少栈溢出尾递归优化Python不支持了解即可5.3 替代方案递归转迭代六、递归的适用场景与注意事项6.1 适用场景6.2 注意事项必避坑七、练习题目巩固提升八、总结一、递归的核心概念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的和需求编写一个递归函数计算123...n的和。分析终止条件当n1时和为1最小规模的问题可直接解决。递归调用n的和 n (1到n-1的和)将原问题拆解为“n”和“1到n-1的和”规模缩小。def sum_recursion(n): # 终止条件n1时返回1 if n 1: return 1 # 递归调用n 前n-1个数的和规模缩小 else: return n sum_recursion(n - 1) # 测试 print(sum_recursion(5)) # 输出1512345执行流程拆解以n5为例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 → 213 → 336 → 4610 → 51015最终返回15。三、Python递归的经典实例必练以下实例覆盖递归的常见应用场景从基础到进阶帮助你理解递归的核心逻辑建议逐行拆解代码、手动模拟执行流程。实例1阶乘计算基础阶乘定义n! n × (n-1) × (n-2) × ... × 1且0! 11! 1。分析终止条件n0或n1时返回1。递归调用n! n × (n-1)!规模缩小为n-1。def factorial(n): # 终止条件n0或n1返回1 if n in (0, 1): return 1 # 递归调用n × (n-1)! else: return n * factorial(n - 1) # 测试 print(factorial(5)) # 输出1205×4×3×2×1 print(factorial(0)) # 输出1符合阶乘定义实例2斐波那契数列进阶斐波那契数列定义从第3项开始每一项都等于前两项之和即1, 1, 2, 3, 5, 8, 13, ...需求编写递归函数求第n项斐波那契数n≥1。分析终止条件n1或n2时返回1前两项固定为1。递归调用第n项 第(n-1)项 第(n-2)项规模缩小为n-1和n-2。def fibonacci(n): # 终止条件n1或n2返回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(maxsizeNone) # maxsizeNone表示无限制缓存 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, a1, b1): 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→n1否则无法到达终止条件。避免重复计算对于重复计算严重的场景使用记忆化缓存或迭代优化。控制递归深度Python默认递归深度有限超过1000需考虑迭代或手动修改递归深度不推荐。# 不推荐手动修改递归深度可能导致内存溢出 import sys sys.setrecursionlimit(2000) # 将递归深度改为2000 test_depth(1500) # 此时可正常执行七、练习题目巩固提升以下练习从易到难建议独立完成巩固递归的核心逻辑编写递归函数求两个正整数的最大公约数GCD提示使用辗转相除法gcd(a,b) gcd(b, a%b)终止条件b0时返回a。编写递归函数计算1到n的乘积即阶乘的变种与实例1呼应。编写递归函数判断一个字符串是否是回文如abba是回文abc不是回文。进阶使用递归实现快速排序Quick Sort核心逻辑选择一个基准值将数组分为“小于基准”和“大于基准”两部分分别递归排序最后合并。练习提示遇到困难时先拆解问题、确定终止条件再编写递归调用手动模拟小规模输入的执行流程逐步调试。八、总结递归是Python中重要的编程思想核心是“分而治之”关键在于把握“终止条件”和“递归调用”两个要素。学习递归的重点的是理解执行流程、拆解问题、避免坑点。初期可通过手动模拟执行流程如阶乘、斐波那契熟悉递归的逻辑后期可结合缓存、迭代等优化方法解决实际开发中的问题。记住递归不是目的而是一种工具——当它能让代码更简洁、逻辑更清晰时使用当它导致效率低下或栈溢出时可考虑迭代等替代方案。