本文目录导读：
我来详细介绍Python递归算法的实现方法和经典案例。
什么是递归
递归是一种函数调用自身的编程技巧,包含两个核心要素：
- 递归基（终止条件）：停止递归的条件
- 递归步骤：将问题分解为更小规模的同类问题
经典递归案例
阶乘计算
def factorial(n):
"""
计算n的阶乘
终止条件：n <= 1时返回1
递归步骤：n * factorial(n-1)
"""
# 递归基
if n <= 1:
return 1
# 递归步骤
return n * factorial(n - 1)
# 测试
print(factorial(5)) # 输出: 120 (5*4*3*2*1)
斐波那契数列
def fibonacci(n):
"""
计算斐波那契数列第n项
终止条件：n <= 1时返回n
递归步骤：fibonacci(n-1) + fibonacci(n-2)
"""
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
# 测试
for i in range(10):
print(fibonacci(i), end=" ") # 输出: 0 1 1 2 3 5 8 13 21 34
汉诺塔问题
def hanoi(n, source, target, auxiliary):
"""
汉诺塔问题
n: 盘子数量
source: 源柱子
target: 目标柱子
auxiliary: 辅助柱子
"""
if n == 1:
print(f"将盘子1从{source}移动到{target}")
return
# 将n-1个盘子从source移动到auxiliary
hanoi(n - 1, source, auxiliary, target)
# 将最大的盘子移动到target
print(f"将盘子{n}从{source}移动到{target}")
# 将n-1个盘子从auxiliary移动到target
hanoi(n - 1, auxiliary, target, source)
# 测试
hanoi(3, 'A', 'C', 'B')
二叉树遍历
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def inorder_traversal(root):
"""
二叉树中序遍历
"""
if root is None:
return []
result = []
# 遍历左子树
result.extend(inorder_traversal(root.left))
# 访问根节点
result.append(root.value)
# 遍历右子树
result.extend(inorder_traversal(root.right))
return result
# 创建测试二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(inorder_traversal(root)) # 输出: [4, 2, 5, 1, 3]
快速排序
def quick_sort(arr):
"""
快速排序递归实现
"""
if len(arr) <= 1:
return arr
pivot = arr[0]
less = [x for x in arr[1:] if x <= pivot]
greater = [x for x in arr[1:] if x > pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)
# 测试
arr = [3, 6, 8, 10, 1, 2, 1]
print(quick_sort(arr)) # 输出: [1, 1, 2, 3, 6, 8, 10]
文件目录遍历
import os
def list_files(path, indent=0):
"""
递归遍历文件目录
"""
items = os.listdir(path)
for item in items:
full_path = os.path.join(path, item)
if os.path.isdir(full_path):
print(" " * indent + f"📁 {item}/")
list_files(full_path, indent + 2)
else:
print(" " * indent + f"📄 {item}")
# 测试（请确保路径存在）
# list_files(".")
递归的优缺点
优点
- 代码简洁：表达逻辑清晰
- 易于理解：符合数学归纳思维
- 处理树形结构：天生适合处理递归定义的数据结构
缺点
- 性能开销：函数调用有额外开销
- 栈溢出风险：递归深度过大可能导致栈溢出
- 重复计算：如朴素斐波那契有大量重复计算
优化技巧
尾递归优化
def factorial_tail(n, accumulator=1):
"""
尾递归优化的阶乘
"""
if n <= 1:
return accumulator
return factorial_tail(n - 1, n * accumulator)
# Python默认不支持尾递归优化，但这是一个好的编程习惯
记忆化递归
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci_memo(n):
"""
使用缓存优化的斐波那契
"""
if n <= 1:
return n
return fibonacci_memo(n - 1) + fibonacci_memo(n - 2)
# 测试
print(fibonacci_memo(100)) # 快速计算
递归的调试技巧
def factorial_debug(n, depth=0):
"""带调试信息的阶乘"""
indent = " " * depth
print(f"{indent}factorial({n}) 被调用")
if n <= 1:
print(f"{indent}返回 1")
return 1
result = n * factorial_debug(n - 1, depth + 1)
print(f"{indent}返回 {result}")
return result
# 测试
factorial_debug(5)
实践建议
- 明确终止条件：确保递归能结束
- 缩小问题规模：每次递归都向终止条件靠近
- 考虑性能：深度较大时考虑迭代替代
- 设置递归深度：
sys.setrecursionlimit(10000) - 优先使用迭代：递归不总是最佳选择
掌握这些案例，你就基本理解了Python递归的核心用法，建议先从简单案例开始,逐步理解递归思维。
