AI开发 - 算法基础 递归 的概念和入门（三）递归的进阶学习

devtools/2025/1/13 13:02:20/

前面我们通过2篇文章，一起了解了 递归，以及使用递归来解决汉诺塔问题。今天我们在这个基础上，进一步地熟悉和学习递归。 

这篇学习笔记将涵盖递归的基本概念、应用、优化技巧、陷阱及与迭代的对比，并通过具体的 Python 代码示例和大家一起来深入理解递归的使用。

一、 巩固基础

1. 递归的概念

递归，简单来说就是函数自己调用自己。听起来有点绕，但其实就像俄罗斯套娃，一层套一层，直到遇到最小的那个娃娃（基线条件）才停止。

递归是指一个函数直接或间接地调用自身。它通常由两个关键要素构成：

  • 基线条件（Base Case）：递归结束的条件，防止无限递归。
  • 递归条件（Recursive Case）：将问题分解成更小的子问题，并递归调用自身来解决这些子问题。
2. 递归的调用栈

每次递归调用都会把当前的局部变量、返回地址等压入调用栈，直到达到基线条件并开始回溯。理解调用栈有助于调试递归程序。

3. 示例：阶乘与斐波那契数列
  • 阶乘：

阶乘是一个经典的递归例子，定义为 n! = n * (n-1)!，直到 1! = 1。

def factorial(n):if n == 0:  # 基线条件return 1else:return n * factorial(n - 1)  # 递归条件

调用 factorial(5) 会通过递归逐步调用直到 factorial(0)，然后逐步返回结果。

想象一下，计算5的阶乘：

  1. factorial(5) 调用 factorial(4)

  2. factorial(4) 调用 factorial(3)

  3. factorial(3) 调用 factorial(2)

  4. factorial(2) 调用 factorial(1)

  5. factorial(1) 调用 factorial(0)

  6. factorial(0) 遇到基线条件，返回1

  7. 然后逐层返回，最终得到 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 nelse:return fibonacci(n - 1) + fibonacci(n - 2)
4. 使用调试工具可视化递归调用栈

可以通过调试工具（例如 PyCharm 或 VS Code 的调试器）逐步观察递归调用栈。每进入一次递归，都会看到栈中增加一个新的调用帧，直到基线条件触发。

也使用调试工具例如Python的pdb，可以一步步跟踪递归函数的执行过程，观察每次调用时变量的变化，帮助你更直观地理解递归。

二、 递归的应用场景

递归在算法设计中就像一把瑞士军刀，可以解决各种问题。递归在很多经典算法中都有广泛应用：

1. 分治法

分治法的精髓在于“分而治之”，把大问题拆解成小问题，分别解决后再合并结果。

  • 归并排序：

归并排序是一种典型的分治算法，通过递归地将数组分成两半进行排序，然后合并已排序的两部分。

def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr) // 2left = 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 arrpivot = 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 Falsereturn 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. 运行流程

  1. 初始化一个大小为n的棋盘board，所有值初始化为-1（表示未放置皇后）。

  2. 调用backtrack(0)，从第0行开始尝试放置皇后。

  3. 在backtrack函数中：

    • 如果当前行row == n，说明找到一种合法布局，将其保存到solutions中。

    • 否则，遍历当前行的每一列，尝试放置皇后：

      • 如果当前位置合法，则放置皇后，并递归处理下一行。

      • 递归结束后，撤销当前行的皇后放置，尝试其他列。

  4. 最终返回所有合法的棋盘布局solutions。

3. 树的遍历

树形结构本身就是递归的天然应用。二叉树的前序、中序、后序遍历都可以通过递归实现。

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef 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 nmemo[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 accreturn 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)returnfor i in range(start, n + 1):backtrack(i + 1, path + [i])backtrack(1, [])return res

继续扩展递归应用，我们将通过实际问题来进一步理解递归的强大功能。

以下是我们一起来使用递归解决的三个实际问题：文件目录遍历、JSON 数据解析 和 HTML 文档解析。

6.1. 文件目录遍历

文件目录遍历是一个常见的递归问题，因为目录可以包含文件和子目录，而子目录又可能包含更多的文件和子目录。因此，我们可以通过递归来遍历整个文件树。

代码示例：递归遍历文件夹

import osdef 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 HTMLParserclass 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

  • 从简单的例子开始，逐步深入理解递归。

  • 多动手实践，尝试用递归解决不同的问题。

  • 不要害怕犯错，调试是学习递归的重要部分。

通过以上内容，我们已经将递归的基础知识和应用场景进行了充分阐述，后续我们就可以通过实际练习不断提升递归的能力。祝你好运！


http://www.ppmy.cn/devtools/150153.html

相关文章

Github出现复杂问题 无法合并 分支冲突太多 如何复原

Github出现复杂问题 无法合并 分支冲突太多 如何复原

目录 问题再现 解决思路 当然我所指的是在 main 分支开一个新的分支 删除本地文件夹 重新克隆 开一个新分支 切换分支 下载远程分支 文件覆盖 合并到主分支 ​​​​​​​问题再现 太复杂了 无法更改 编译器现状 全部崩溃了 无法更改 即使创建一个新的分支也无济于…
阅读更多...
Pytest-Bdd-Playwright 系列教程（完结篇）：本框架的功能参数说明

Pytest-Bdd-Playwright 系列教程（完结篇）：本框架的功能参数说明

Pytest-Bdd-Playwright 系列教程&#xff08;完结篇&#xff09;&#xff1a;本框架的功能参数说明 简介1. 浏览器设置2. 环境与设备配置3. 存储状态管理4. 测试用例筛选5. 并行与重试控制6. 报告生成与输出格式7. 其他功能附录&#xff1a;参数说明表 简介 本框架支持多种浏览…
阅读更多...
从攻击视角探讨ChatGPT对网络安全的影响

从攻击视角探讨ChatGPT对网络安全的影响

ChatGPT是OpenAI 发布的基于人工智能的对话机器人&#xff0c;上线短短2个月活跃用户就突破了1亿&#xff0c;成为全球关注的焦点。ChatGPT可以自动化地处理对话&#xff0c;可以通过基于自然语言处理技术的模型、情景模型和语言模型来自动生成文章&#xff0c;甚至可以按照用户…
阅读更多...
Kafka优势剖析-流处理集成

Kafka优势剖析-流处理集成

目录 1. Kafka Streams API 1.1 什么是 Kafka Streams API&#xff1f; 1.2 Kafka Streams 的工作原理 1.3 Kafka Streams 的优势 1.4 Kafka Streams 的典型应用场景 2. KSQL 2.1 什么是 KSQL&#xff1f; 2.2 KSQL 的工作原理 2.3 KSQL 的优势 Kafka 的流处理能力是其…
阅读更多...
【数据库】四、数据库管理与维护

【数据库】四、数据库管理与维护

文章目录 四、数据库管理与维护1 安全性管理2 事务概述3 并发控制4 备份与恢复管理 四、数据库管理与维护 1 安全性管理 安全性管理是指保护数据库&#xff0c;以避免非法用户进行窃取数据、篡改数据、删除数据和破坏数据库结构等操作 三个级别认证&#xff1a; 服务器级别…
阅读更多...
C# 继承(接口)

C# 继承(接口)

接口 如果一个类派生与一个接口&#xff0c;它就会执行某些函数。并不是所有的面向对象语言都支持接口。 熟悉COM的开发人员应注意&#xff0c;尽管在概念上C#接口类似于COM接口&#xff0c;但他们是不筒的&#xff0c;底层的结构不筒。比如&#xff0c;C#接口并不派生于IUnko…
阅读更多...
安卓开发动画

安卓开发动画

1.gif图片动画 边缘会有锯齿 2.json动画 用lottie json文件动画 实现 Android Studio使用lottie&#xff0c;加载json文件&#xff0c;实现动画效果_android 加载json动画-CSDN博客 遇到的坑 1.不播放&#xff0c;可能因为设置了图片&#xff08;跟动画一样的图片&#xf…
阅读更多...
《拉依达的嵌入式\驱动面试宝典》—操作系统篇(三)

《拉依达的嵌入式\驱动面试宝典》—操作系统篇(三)

《拉依达的嵌入式\驱动面试宝典》—操作系统篇(三) 你好，我是拉依达。 感谢所有阅读关注我的同学支持，目前博客累计阅读 27w，关注1.5w人。其中博客《最全Linux驱动开发全流程详细解析（持续更新）-CSDN博客》已经是 Linux驱动 相关内容搜索的推荐首位，感谢大家支持。 《拉…
阅读更多...
最新文章

Copyright @ 2022~2023