AI开发 - 算法基础 递归 的概念和入门（三）递归的进阶学习
前面我们通过2篇文章，一起了解了 递归，以及使用递归来解决汉诺塔问题。今天我们在这个基础上，进一步地熟悉和学习递归。
这篇学习笔记将涵盖递归的基本概念、应用、优化技巧、陷阱及与迭代的对比，并通过具体的 Python 代码示例和大家一起来深入理解递归的使用。
一、 巩固基础
1. 递归的概念
递归，简单来说就是函数自己调用自己。听起来有点绕，但其实就像俄罗斯套娃，一层套一层，直到遇到最小的那个娃娃（基线条件）才停止。
递归是指一个函数直接或间接地调用自身。它通常由两个关键要素构成：
- 基线条件（Base Case）：递归结束的条件，防止无限递归。
- 递归条件（Recursive Case）：将问题分解成更小的子问题，并递归调用自身来解决这些子问题。
2. 递归的调用栈
每次递归调用都会把当前的局部变量、返回地址等压入调用栈，直到达到基线条件并开始回溯。理解调用栈有助于调试递归程序。
3. 示例：阶乘与斐波那契数列
- 阶乘：
阶乘是一个经典的递归例子，定义为 n! = n * (n-1)!，直到 1! = 1。
def factorial(n):
if n == 0: # 基线条件
return 1
else:
return n * factorial(n - 1) # 递归条件
调用 factorial(5) 会通过递归逐步调用直到 factorial(0)，然后逐步返回结果。
想象一下，计算5的阶乘：
-
factorial(5)调用factorial(4) -
factorial(4)调用factorial(3) -
factorial(3)调用factorial(2) -
factorial(2)调用factorial(1) -
factorial(1)调用factorial(0) -
factorial(0)遇到基线条件，返回1 -
然后逐层返回，最终得到
5 * 4 * 3 * 2 * 1 * 1 = 120
- 斐波那契数列：
斐波那契数列的递归定义为 F(n) = F(n-1) + F(n-2)，直到 F(0) = 0 和 F(1) = 1。
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2)
4. 使用调试工具可视化递归调用栈
可以通过调试工具（例如 PyCharm 或 VS Code 的调试器）逐步观察递归调用栈。每进入一次递归，都会看到栈中增加一个新的调用帧，直到基线条件触发。
也使用调试工具例如Python的pdb，可以一步步跟踪递归函数的执行过程，观察每次调用时变量的变化，帮助你更直观地理解递归。
二、 递归的应用场景
递归在算法设计中就像一把瑞士军刀，可以解决各种问题。递归在很多经典算法中都有广泛应用：
1. 分治法
分治法的精髓在于“分而治之”，把大问题拆解成小问题，分别解决后再合并结果。
- 归并排序：
归并排序是一种典型的分治算法，通过递归地将数组分成两半进行排序，然后合并已排序的两部分。
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
while left and right:
if left[0] < right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
result.extend(left)
result.extend(right)
return result
- 快速排序：
快速排序通过递归地选择一个基准元素，将数组分为比基准小和比基准大的两部分，然后对这两部分分别进行排序。
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
2. 回溯法
回溯法是通过递归尝试所有可能的解，并在遇到错误时回退并继续尝试其他解。
- 八皇后问题：
通过递归摆放皇后，并判断每一层是否满足规则。如果满足规则就进入下一层，否则回退。
八皇后问题是一个经典的回溯算法问题，目标是在一个8x8的棋盘上放置8个皇后，使得它们互不攻击（即任意两个皇后不能在同一行、同一列或同一对角线上）。
def solve_n_queens(n):
# 初始化棋盘，-1表示未放置皇后
board = [-1] * n
# 存储所有合法的棋盘布局
solutions = []
# 回溯函数
def backtrack(row):
# 如果已经放置了n个皇后，保存当前棋盘布局
if row == n:
solutions.append(board[:])
return
# 尝试在当前行的每一列放置皇后
for col in range(n):
# 检查当前位置是否合法
if is_valid(board, row, col):
# 放置皇后
board[row] = col
# 递归处理下一行
backtrack(row + 1)
# 回溯：撤销当前行的皇后放置
board[row] = -1
# 检查在第row行第col列放置皇后是否合法
def is_valid(board, row, col):
# 遍历之前的所有行
for i in range(row):
# 检查是否在同一列或同一对角线上
if board[i] == col or abs(board[i] - col) == row - i:
return False
return True
# 从第0行开始回溯
backtrack(0)
# 返回所有合法的棋盘布局
return solutions代码解析
2.1. 数据结构
-
board: 一个长度为n的列表，表示棋盘。board[i] = j表示在第i行第j列放置了一个皇后。 -
solutions: 存储所有合法的棋盘布局。
2.2. 核心函数
-
backtrack(row): 递归回溯函数，尝试在第row行放置皇后。-
如果
row == n，说明已经成功放置了n个皇后，将当前棋盘布局保存到solutions中。 -
否则，遍历当前行的每一列，尝试放置皇后：
-
如果当前位置合法（通过
is_valid检查），则放置皇后，并递归处理下一行。 -
递归结束后，撤销当前行的皇后放置（回溯），尝试其他可能性。
-
-
-
is_valid(board, row, col): 检查在第row行第col列放置皇后是否合法。-
遍历之前的所有行，检查是否有皇后在同一列或同一对角线上。
-
2.3. 运行流程
-
初始化一个大小为
n的棋盘board，所有值初始化为-1（表示未放置皇后）。 -
调用
backtrack(0)，从第0行开始尝试放置皇后。 -
在
backtrack函数中：-
如果当前行
row == n，说明找到一种合法布局，将其保存到solutions中。 -
否则，遍历当前行的每一列，尝试放置皇后：
-
如果当前位置合法，则放置皇后，并递归处理下一行。
-
递归结束后，撤销当前行的皇后放置，尝试其他列。
-
-
-
最终返回所有合法的棋盘布局
solutions。
3. 树的遍历
树形结构本身就是递归的天然应用。二叉树的前序、中序、后序遍历都可以通过递归实现。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder(root):
if root:
print(root.val)
preorder(root.left)
preorder(root.right)
三、 递归的优化
1. 记忆化搜索
记忆化搜索是一种优化递归的技术，目的是避免重复计算相同的子问题。常用于斐波那契数列等问题。
def fibonacci_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
return memo[n]
2. 尾递归优化
尾递归是指递归调用出现在函数的最后一步，可以将递归转化为循环，从而避免栈溢出问题。
def factorial_tail(n, acc=1):
if n == 0:
return acc
return factorial_tail(n - 1, n * acc)
各位需要注意的是：Python 并不支持尾递归优化，因此对于深度较大的递归，仍然要小心栈溢出。
四、 递归的陷阱
1. 栈溢出
递归深度过大时，调用栈会导致栈溢出。可以通过增加基线条件或者将递归转化为迭代来避免。
2. 重复计算
递归可能会多次计算相同的子问题，造成效率低下。例如，斐波那契数列的递归实现会计算许多重复的子问题。
3. 效率低下
递归相较于循环通常会带来额外的函数调用开销，导致效率较低。
五、 递归与迭代
递归和迭代各有优缺点：
- 递归在处理分治问题、树的遍历等复杂问题时非常直观。
- 迭代相对效率更高，特别是对于简单问题，如阶乘、斐波那契数列。
有些递归问题可以转化为迭代解决，特别是尾递归问题。
六、 实践项目
递归在实际问题中有广泛应用。以下是几个经典递归问题：
- 全排列：给定一组数字，输出所有可能的排列。
- 组合问题：从一个集合中选取若干元素的所有组合。
- 子集问题：从一个集合中生成所有的子集。
# 组合问题示例
def combine(n, k):
res = []
def backtrack(start, path):
if len(path) == k:
res.append(path)
return
for i in range(start, n + 1):
backtrack(i + 1, path + [i])
backtrack(1, [])
return res
继续扩展递归应用，我们将通过实际问题来进一步理解递归的强大功能。
以下是我们一起来使用递归解决的三个实际问题：文件目录遍历、JSON 数据解析 和 HTML 文档解析。
6.1. 文件目录遍历
文件目录遍历是一个常见的递归问题，因为目录可以包含文件和子目录，而子目录又可能包含更多的文件和子目录。因此，我们可以通过递归来遍历整个文件树。
代码示例：递归遍历文件夹
import os
def traverse_directory(path):
# 获取路径下的所有文件和子目录
for item in os.listdir(path):
full_path = os.path.join(path, item)
if os.path.isdir(full_path): # 如果是目录，递归遍历
print(f"Directory: {full_path}")
traverse_directory(full_path) # 递归调用
else: # 如果是文件，打印文件路径
print(f"File: {full_path}")
# 示例调用
traverse_directory('/path/to/directory')
解释：
os.listdir(path)返回指定目录下的所有文件和子目录的名称。os.path.isdir(full_path)判断路径是否是一个目录。- 如果是目录，则递归调用
traverse_directory，遍历该目录。 - 如果是文件，则直接打印文件路径。
通过这种方式，可以遍历整个文件树，不管目录有多深，这个非常实用！
6.2. JSON 数据解析
递归常常用于处理具有嵌套结构的数据，像 JSON 这样的格式通常包含字典、列表等复杂嵌套结构。使用递归可以帮助我们解析和提取其中的数据。
代码示例：递归解析 JSON 数据
假设我们有一个复杂的 JSON 数据，其中包含嵌套的字典和列表。
import json
# 假设的 JSON 数据
data = '''
{
"name": "Alice",
"age": 25,
"address": {
"city": "Wonderland",
"zipcode": "12345"
},
"hobbies": ["reading", "painting", {"name": "sports", "types": ["soccer", "basketball"]}]
}
'''
def parse_json(obj):
if isinstance(obj, dict):
for key, value in obj.items():
print(f"{key}:")
parse_json(value) # 递归调用，处理字典的每个值
elif isinstance(obj, list):
for item in obj:
parse_json(item) # 递归调用，处理列表中的每个元素
else:
print(f"Value: {obj}") # 打印最终的值
# 解析 JSON 数据
parse_json(json.loads(data))
解释：
parse_json函数检查对象类型：- 如果是字典，就递归地遍历字典的键值对。
- 如果是列表，就递归地遍历列表中的元素。
- 如果既不是字典也不是列表，那么就是基本数据类型，直接打印值。
- 使用
json.loads将字符串转换为 Python 对象后传递给parse_json进行解析。
这种递归解析方法适用于处理结构复杂的 JSON 数据，能够处理不确定的深度和层级。
6.3. HTML 文档解析
HTML 文档通常是由标签嵌套构成的树形结构，因此解析 HTML 时递归是非常自然的选择。我们可以使用递归遍历 HTML 元素及其子元素。
代码示例：递归解析 HTML 文档
假设我们需要解析一个简单的 HTML 文件，提取其中的所有 a 标签（超链接）。
from html.parser import HTMLParser
class MyHTMLParser(HTMLParser):
def handle_starttag(self, tag, attrs):
if tag == 'a': # 如果是 <a> 标签
for attr in attrs:
if attr[0] == 'href':
print(f"Link: {attr[1]}") # 打印链接地址
# 示例 HTML 文档
html_data = '''
<html>
<head><title>Test Page</title></head>
<body>
<h1>Welcome to My Webpage</h1>
<p>Here are some links:</p>
<a href="https://example.com">Example</a>
<a href="https://another-example.com">Another Example</a>
</body>
</html>
'''
# 创建并使用 HTMLParser 对象
parser = MyHTMLParser()
parser.feed(html_data)
解释：
HTMLParser是 Python 的标准库，用于解析 HTML 内容。handle_starttag方法在每次遇到开始标签时被调用。当标签是a时，我们从其属性中提取href，即超链接地址。feed方法将 HTML 字符串传递给解析器，递归解析 HTML 内容并提取超链接。
在实际的 HTML 解析中，递归处理各个标签及其子标签是非常常见的，尤其是当文档结构复杂时。
七、 拓展学习
拓展学习可以让我们在理解和掌握递归的基础上，进行融汇贯通，将递归运用在实际需要的地方。
一点建议:
- 函数式编程：学习函数式编程语言，如 Haskell 或 Lisp，有助于深入理解递归的思想。
- 数学归纳法：递归和数学归纳法密切相关，理解递归关系式和数学归纳法的原理有助于深入理解递归的本质。
-
学习递归相关的数学知识，例如：
-
递归关系式
-
数学归纳法
-
-
学习资源:
-
书籍:
-
《算法导论》
-
《编程珠玑》
-
-
网站:
-
LeetCode
-
LintCode
-
-
视频:
-
MIT OpenCourseware: Introduction to Algorithms
-
-
从简单的例子开始，逐步深入理解递归。
-
多动手实践，尝试用递归解决不同的问题。
-
不要害怕犯错，调试是学习递归的重要部分。
通过以上内容，我们已经将递归的基础知识和应用场景进行了充分阐述，后续我们就可以通过实际练习不断提升递归的能力。祝你好运！