递归

前言

递归是一种在编程中广泛使用的技术，通过函数调用自身来解决问题。本章详细讲解了 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 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'

【分析】

①基准情况：

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

②递归情况：

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