Python学不会来打我(28)递归函数：从基础到实战一篇讲清所有知识

欢迎大家来到IT世界,在知识的湖畔探索吧!

在Python编程中，递归函数（Recursive Function） 是一种非常强大且优雅的编程技巧。它通过函数自身调用自身的方式，将复杂问题分解为更小、结构相似的子问题来解决。

本文将详细讲解 Python递归函数的基本概念、使用方法、递归终止条件、常见应用场景，并通过大量示例帮助你掌握这一重要技能。

欢迎大家来到IT世界,在知识的湖畔探索吧!

一、什么是递归函数？

递归函数是指在函数体内调用自身的函数。

换句话说，一个函数如果在其定义中直接或间接地调用了自己，就称为递归函数。

递归的两个基本要素：

1. 基准条件（Base Case）：这是递归的结束条件，用于防止无限递归。
2. 递归步骤（Recursive Step）：将大问题分解成更小的问题，并调用函数处理这些小问题。

✅ 示例：计算阶乘的递归函数

def factorial(n): if n == 0: # 基准条件 return 1 else: return n * factorial(n - 1) # 递归调用 print(factorial(5)) # 输出：120

欢迎大家来到IT世界,在知识的湖畔探索吧!

二、递归函数的工作原理

递归函数的本质是函数调用栈的层层嵌套。每次递归调用都会将当前状态压入调用栈，直到达到基准条件后开始逐层返回结果。

递归调用过程分析：

以 factorial(3) 为例：

欢迎大家来到IT世界,在知识的湖畔探索吧!factorial(3) = 3 * factorial(2) = 3 * (2 * factorial(1)) = 3 * (2 * (1 * factorial(0))) = 3 * (2 * (1 * 1)) = 6

可以看到，递归函数会不断拆解问题，直到遇到基准条件后再逐步回溯计算结果。

三、递归函数的优点与缺点

四、递归函数的使用场景

场景1：数学问题求解

许多数学问题天然具有递归结构，例如：

• 阶乘
• 斐波那契数列
• 汉诺塔问题
• 排列组合

示例：斐波那契数列

def fibonacci(n): if n <= 1: return n else: return fibonacci(n - 1) + fibonacci(n - 2) print(fibonacci(7)) # 输出：13

场景2：文件系统操作（如目录遍历）

递归非常适合用来遍历目录及其子目录中的所有文件。

示例：递归遍历目录

欢迎大家来到IT世界,在知识的湖畔探索吧!import os def list_files(path): for item in os.listdir(path): full_path = os.path.join(path, item) if os.path.isdir(full_path): print(f"进入目录：{full_path}") list_files(full_path) else: print(f"文件：{full_path}") # 注意：请替换为你自己的路径 # list_files("/your/path")

场景3：树与图的遍历（深度优先搜索DFS）

递归是实现深度优先搜索（DFS）最自然的方式之一。

示例：二叉树的前序遍历

class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None def preorder(root): if root is None: return print(root.val) preorder(root.left) preorder(root.right) # 构建简单二叉树 # A # / \ # B C root = TreeNode("A") root.left = TreeNode("B") root.right = TreeNode("C") preorder(root)

输出：

欢迎大家来到IT世界,在知识的湖畔探索吧!A B C

场景4：字符串/数组的组合与排列生成

递归可以用来生成所有可能的排列组合。

示例：生成字符串的所有排列

def permute(s): result = [] def backtrack(path, remaining): if not remaining: result.append(path) return for i in range(len(remaining)): backtrack(path + remaining[i], remaining[:i] + remaining[i+1:]) backtrack("", s) return result print(permute("abc"))

输出：

欢迎大家来到IT世界,在知识的湖畔探索吧!['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

五、递归函数的注意事项

1. 必须有明确的终止条件

没有基准条件或基准条件不正确，会导致无限递归，最终抛出 RecursionError 错误。

❌ 错误示例：

def infinite_recursion(): print("无限递归！") infinite_recursion() infinite_recursion() # 报错：RecursionError: maximum recursion depth exceeded

2. 控制递归深度

Python默认的最大递归深度为1000，超过会报错。可以通过以下方式修改：

欢迎大家来到IT世界,在知识的湖畔探索吧!import sys sys.setrecursionlimit(2000) # 修改最大递归深度

但不建议频繁修改，应尽量优化算法逻辑减少递归层级。

3. 避免重复计算（如斐波那契数列）

递归版本的斐波那契存在大量重复计算，效率极低。可通过记忆化递归或动态规划优化。

记忆化递归版斐波那契：

from functools import lru_cache @lru_cache(maxsize=None) def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2) print(fib(100)) # 输出：

六、递归与迭代的比较

七、递归函数的最佳实践

八、总结

递归函数是Python中最强大的编程工具之一，它让我们可以用简洁优雅的方式解决复杂的结构性问题。

通过本文的学习，你应该已经掌握了：

• 什么是递归函数，以及它的两个基本要素（基准条件和递归步骤）
• 递归函数的调用过程和工作原理
• 递归函数的实际应用场景（数学、文件操作、树结构、字符串组合等）
• 递归函数的优缺点及最佳实践

作为Python初学者，建议你在练习中多尝试使用递归函数，理解其在不同场景下的行为差异。随着学习的深入，你会发现递归函数在实际项目中的广泛应用。

希望本文能帮助你全面掌握Python递归函数的相关知识，并在今后的编程实践中灵活运用！