前言
递归是一种在编程中广泛使用的技术，通过函数调用自身来解决问题。本章详细讲解了 Python 中递归的基本原理以及应用场景。
一、基本概述
①定义
递归指一个函数在其定义中直接或间接调用自身。递归问题通常可以分解成多个相似的子问题，从而简化复杂问题的求解。
递归通常由两部分组成：
- 基准情况（Base Case）：递归的终止条件。
- 递归情况（Recursive Case）：函数调用自身的部分，通常用于处理问题的子集。
递归的核心思想是将问题拆解为更小、更简单的子问题，直到达到基准情况。
②应用场景
- 树结构遍历： 树形结构，如文件系统、组织结构图、解析树等，通常使用递归来遍历或操作每个节点。
- 图的深度优先搜索（DFS）： 在图的遍历中，递归可以用来实现深度优先搜索算法，适用于查找图中的路径、连通分量等。
- 分治算法： 许多经典的分治算法，如快速排序、归并排序，使用递归来将问题分解为更小的子问题，然后合并解决方案。
- 数学计算： 一些数学计算问题自然适合用递归解决，如阶乘、斐波那契数列等。
二、案例分析
【案例一：斐波那契数列】
斐波那契数列的定义如下：
F(0) = 0
F(1) = 1
F(n) = F(n-1) F(n-2)，当 n > 1
请使用递归计算斐波那契数列。
代码语言：python代码运行次数：0复制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) 时，代码会按照递归的方式逐步计算：
代码语言：txt复制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 文件夹中的全部文件。
代码语言：python代码运行次数：0复制import os
def 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 "/" f
if 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_list
if __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'
【分析】
①基准情况：
- 目录不存在：函数需要终止递归，因为没有更多的目录可以处理。函数打印错误并返回空列表。
- 目录为空：虽然不需要递归，但函数仍需处理这种情况以返回结果。函数返回包含找到的文件（如果有）的列表
②递归情况：
- 处理子目录：递归调用自身来处理子目录中的文件。
- 处理文件：将文件路径添加到结果列表中。
