Chapter 42 递归

本文主要是介绍Chapter 42 递归，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

欢迎大家订阅【Python从入门到精通】专栏，一起探索Python的无限可能！

---

前言

递归是一种在编程中广泛使用的技术，通过让函数调用自身来逐步解决问题。本章详细讲解了 Python 中递归的基本原理以及应用场景。

---

一、基本概述

①定义
递归指一个函数在其定义中直接或间接调用自身。递归问题通常可以分解成多个相似的子问题，从而简化复杂问题的求解。

递归通常由两部分组成：

• 基准情况（Base Case）：递归的终止条件。
• 递归情况（Recursive Case）：函数调用自身的部分，通常用于处理问题的子集。

递归的核心思想是将问题拆解为更小、更简单的子问题，直到达到基准情况。

②应用场景

• 树结构遍历：
  树形结构，如文件系统、组织结构图、解析树等，通常使用递归来遍历或操作每个节点。
• 图的深度优先搜索（DFS）：
  在图的遍历中，递归可以用来实现深度优先搜索算法，适用于查找图中的路径、连通分量等。
• 分治算法：
  许多经典的分治算法，如快速排序、归并排序，使用递归来将问题分解为更小的子问题，然后合并解决方案。
• 数学计算：
  一些数学计算问题自然适合用递归解决，如阶乘、斐波那契数列等。

二、案例分析

【案例一：斐波那契数列】
斐波那契数列的定义如下：
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)，当 n > 1
请使用递归计算斐波那契数列。

def fibonacci(n):# 基准情况if n <= 1:return n# 递归情况else:return fibonacci(n-1) + fibonacci(n-2)
# 测试
print(fibonacci(10))

输出结果：
55

【分析】
①基准情况：
如果 n 小于或等于 1（即 n == 0 或 n == 1），直接返回 n。这确保了递归在达到最简单的情况时停止。
②递归情况：
对于 n > 1，函数调用自身两次：fibonacci(n-1) 和 fibonacci(n-2)。这是通过递归计算前两个斐波那契数，然后将它们相加，得到当前的斐波那契数。
③计算过程：
调用 fibonacci(10) 时，代码会按照递归的方式逐步计算：

fibonacci(10)-> fibonacci(9) + fibonacci(8)-> (fibonacci(8) + fibonacci(7)) + (fibonacci(7) + fibonacci(6))-> ((fibonacci(7) + fibonacci(6)) + (fibonacci(6) + fibonacci(5))) + ((fibonacci(6) + fibonacci(5)) + (fibonacci(5) + fibonacci(4)))-> ...

这个递归过程会展开成一棵巨大的递归树，每个节点表示一个 fibonacci(n) 的计算。

F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8
F(7) = F(6) + F(5) = 8 + 5 = 13
F(8) = F(7) + F(6) = 13 + 8 = 21
F(9) = F(8) + F(7) = 21 + 13 = 34
F(10) = F(9) + F(8) = 34 + 21 = 55

每个 fibonacci 调用都会递归地计算两个更小的 fibonacci 值，直到达到基准情况。

【案例二：文件项目结构】
如图，在D:/Countries 文件夹内，有如下文件夹以及文本文件：

在D:/Countries/Cities 文件夹内，有如下文本文件：

请使用递归遍历D:/Countries 文件夹中的全部文件。

import osdef test_os():print(os.listdir("D:/test"))        # 列出路径下的内容# print(os.path.isdir("D:/test/a"))   # 判断指定路径是不是文件夹# print(os.path.exists("D:/test"))    # 判断指定路径是否存在def get_files_recursion_from_dir(path):"""从指定的文件夹中使用递归的方式，获取全部的文件列表:param path: 被判断的文件夹:return: list，包含全部的文件，如果目录不存在或者无文件就返回一个空list"""# 初始化一个空列表，用于存储找到的所有文件路径file_list = []if os.path.exists(path):for f in os.listdir(path):new_path = path + "/" + fif os.path.isdir(new_path):# 进入到这里，表明这个目录是文件夹不是文件file_list += get_files_recursion_from_dir(new_path)else:file_list.append(new_path)else:print(f"指定的目录{path}，不存在")return []return file_listif __name__ == '__main__':print(get_files_recursion_from_dir("D:/Countries"))

输出结果：
[‘D:/Countries/A国.txt’, ‘D:/Countries/B国.txt’, ,‘D:/Countries/C国.txt’，‘D:/Countries/Cities/A市.txt’, ‘D:/Countries/Cities/B市.txt’, ‘D:/Countries/Cities/C市.txt’]

【分析】
①基准情况：

• 目录不存在：函数需要终止递归，因为没有更多的目录可以处理。函数打印错误并返回空列表。
• 目录为空：虽然不需要递归，但函数仍需处理这种情况以返回结果。函数返回包含找到的文件（如果有）的列表

②递归情况：

• 处理子目录：递归调用自身来处理子目录中的文件。
• 处理文件：将文件路径添加到结果列表中。

这篇关于Chapter 42 递归的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---