Skip to main content

06-递归函数

1.什么是递归函数？​

递归函数（Recursive Function）是指一个函数直接或间接调用自身，通常用来解决可以被分解为相似子问题的场景。递归的核心思想是”把大问题逐步分解成小问题，直到小到可以直接解决“。

2.递归的核心组成​

  • 基本情况（Base Case）：

递归必须有一个 结束条件，防止无限调用自身，通常称为 递归终止条件。

  • 递归调用（Recursive Case）：

在每次函数调用中，问题的规模会逐步缩小，并递归调用自身，直到满足基本情况。

生动比喻：

想象你站在楼梯的顶端，想知道楼梯有多少级。你可以问站在你下面一阶的人：”楼梯还有多少级？”那个人也会问再下一阶的人。。。。。。直到问到站在楼梯最底下的人，他会说：”这是第一级。“

  • 最底下的人回答 = 基本情况（递归终止条件）
  • 每个人递推上去的答案 = 递归调用

3.示例​

3.1阶乘（Factorial）​

阶乘定义：

  • n! = n * (n-1) * (n-2) * ... * 1
  • 0! = 1（基本情况）
def factorial(n):
    if n == 0:
        return 1 # 基本情况：0的阶乘是1
    else:
        return n * factorial(n - 1) # 递归调用


# 测试
print(factorial(5)) # 输出 120 （5 * 4 * 3 * 2 * 1）

3.2斐波那契数列（Fibonacci Sequence）​

斐波那契数列定义：

  • F(0) = 0, F(1) = 1（基本情况）
  • F(n) = F(n-1) + F(n-2) （递归公式）
def fibonacci(n):
    if n == 0:
        return 0  # 基本情况
    elif n == 1:
        return 1  # 基本情况
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # 递归调用

# 测试
print(fibonacci(6))  # 输出 8 （0, 1, 1, 2, 3, 5, 8）

4.应用场景​

4.1数学问题：​

阶乘、斐波那契数列、幂运算等。

4.2数据结构：​

递归非常适合处理**树（Tree）**和 **图（Graph）**等层次结构的数据，如遍历文件系统或解析JSON数据。

4.3分治算法：​

归并排序（Merge Sort）、快速排序（Quick Sort）等算法使用递归分解大问题为小问题。

4.4动态规划与回溯：​

如 八皇后问题、迷宫寻路、子集和问题等。

5.实际应用​

5.1遍历嵌套文件夹​

import os

def list_files(directory):
    for item in os.listdir(directory):
        path = os.path.join(directory, item)
        if os.path.isdir(path):
            list_files(path)  # 递归调用，遍历子文件夹
        else:
            print(path)  # 输出文件路径

# 调用函数
# list_files("/path/to/directory")

5.2迷宫寻路（回溯法）​

def solve_maze(maze, x, y, path):
    if (x, y) == (len(maze)-1, len(maze[0])-1):  # 到达终点
        path.append((x, y))
        return True

    if 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0:
        maze[x][y] = -1  # 标记已访问
        path.append((x, y))

        # 尝试四个方向
        if (solve_maze(maze, x+1, y, path) or
            solve_maze(maze, x, y+1, path) or
            solve_maze(maze, x-1, y, path) or
            solve_maze(maze, x, y-1, path)):
            return True
        
        path.pop()  # 回溯
        maze[x][y] = 0  # 取消标记
    return False

# 0 表示通路，1 表示障碍
maze = [
    [0, 1, 0, 0],
    [0, 0, 0, 1],
    [1, 1, 0, 0],
    [0, 0, 0, 0]
]
path = []
if solve_maze(maze, 0, 0, path):
    print("找到路径:", path)
else:
    print("无解")

6.递归的优缺点​

优点：

  • 代码简洁，逻辑清晰，特别适合层级结构问题。
  • 易于实现复杂算法，如树遍历、图搜索等。

缺点：

  • 性能开销大：每次函数调用会占用栈空间，过深的递归可能导致 栈溢出（RecursionError）。
  • 效率问题：有些递归（如斐波那契数列）会产生大量重复计算，可通过记忆化或动态规划优化。

7.递归与迭代的对比​

递归迭代
代码简洁，易于理解层级结构的问题适合处理线性问题，性能更高
占用更多内存（函数调用栈）占用较少内存
易导致栈溢出，需要考虑终止条件不会有栈溢出的问题
常用于树、图、分治等复杂结构和算法常用于循环、遍历等简单问题

总结​

递归是一种强大的解决问题的方式，尤其适合处理分层、分治和重复子问题的场景。掌握递归不仅能让你用简洁的代码解决复杂问题，还能深入理解很多算法的核心思想。不过，递归需要谨慎使用，注意终止条件和性能优化。