Python递归函数：原理、实现与优化-牛站云

递归函数是 Python 编程中非常重要的一种函数设计方式。它允许函数在执行过程中调用自身，通过不断缩小问题规模，最终将复杂问题拆解成多个结构相同的小问题。树形结构遍历、阶乘计算、斐波那契数列、目录搜索、回溯算法等场景，都可以看到递归的身影。

理解 Python 递归函数的关键，不只是掌握“函数调用自己”的写法，还需要弄清楚递归终止条件、调用栈变化、参数传递以及递归优化等问题。

一、什么是递归函数

递归函数是指函数在自己的函数体中直接或间接调用自身的函数。

一个完整的递归过程通常包含两个核心部分：

递归终止条件：确定什么时候停止继续调用自身。
递归调用逻辑：将当前问题转化成规模更小、结构相同的子问题。

例如计算自然数阶乘：

Python
运行
def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))

执行 factorial(5) 时，函数调用过程大致如下：


factorial(5)
    ↓
5 * factorial(4)
    ↓
5 * 4 * factorial(3)
    ↓
5 * 4 * 3 * factorial(2)
    ↓
5 * 4 * 3 * 2 * factorial(1)
    ↓
120

这里 n == 1 就是递归的终止条件，而 factorial(n - 1) 则负责不断缩小问题规模。

二、Python递归函数的基本原理

递归本质上依赖程序运行时的调用栈。

每调用一次函数，Python 都会为这次调用保存相应的执行环境，包括局部变量、参数以及函数执行位置等信息。

例如：

Python
运行
def count_down(n):
    if n == 0:
        return
    print(n)
    count_down(n - 1)

count_down(3)

执行过程可以理解为：


count_down(3)
    count_down(2)
        count_down(1)
            count_down(0)

当 count_down(0) 满足终止条件并返回后，之前暂停的函数调用会依次恢复执行。

因此，递归通常具有“向下调用、向上返回”的特点。

如果递归深度过大，就会不断占用调用栈空间。Python 为了避免无限递归耗尽系统资源，会限制递归深度。

可以通过以下代码查看当前递归深度限制：

Python
运行
import sys

print(sys.getrecursionlimit())

通常可以使用 sys.setrecursionlimit() 调整限制：

Python
运行
import sys

sys.setrecursionlimit(3000)

不过，简单提高递归限制并不能真正解决算法设计不合理的问题。对于非常深的递归，更推荐考虑改写成循环或显式栈。

三、递归函数的标准结构

一个比较典型的递归函数可以写成：

Python
运行
def recursive_function(data):
    if termination_condition:
        return result

    smaller_data = process(data)
    return recursive_function(smaller_data)

例如求从 1 到 n 的累加和：

Python
运行
def sum_to(n):
    if n <= 0:
        return 0
    return n + sum_to(n - 1)

print(sum_to(5))

计算过程为：


sum_to(5)
= 5 + sum_to(4)
= 5 + 4 + sum_to(3)
= 5 + 4 + 3 + sum_to(2)
= 5 + 4 + 3 + 2 + sum_to(1)
= 15

设计递归函数时，可以按照以下思路分析：

当前问题是什么？
最简单的情况是什么？
最简单情况应该直接返回什么？
如何把当前问题缩小？
缩小后的问题是否仍然可以使用同一个函数解决？

这套思路对于理解递归算法非常有帮助。

四、Python递归实现阶乘

阶乘是最经典的递归案例之一。

数学定义为：


n! = n × (n-1) × (n-2) × ... × 1

递归关系可以表示为：


n! = n × (n-1)!

Python 实现：

Python
运行
def factorial(n):
    if n < 0:
        raise ValueError("n不能为负数")

    if n <= 1:
        return 1

    return n * factorial(n - 1)

调用：

Python
运行
print(factorial(6))

结果：

这种实现非常直观，但如果只是为了计算阶乘，循环通常更加简单：

Python
运行
def factorial(n):
    if n < 0:
        raise ValueError("n不能为负数")

    result = 1

    for i in range(2, n + 1):
        result *= i

    return result

因此，递归并不是所有问题的最佳方案。递归最大的价值往往体现在问题本身具有递归结构的场景。

五、使用递归实现斐波那契数列

斐波那契数列定义如下：


F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

直接使用递归：

Python
运行
def fibonacci(n):
    if n <= 1:
        return n

    return fibonacci(n - 1) + fibonacci(n - 2)

例如：

Python
运行
print(fibonacci(10))

输出：

这种写法虽然非常符合数学定义，但存在严重的性能问题。

例如计算：

Python
运行
fibonacci(5)

会重复计算大量相同结果：


fib(5)
├── fib(4)
│   ├── fib(3)
│   └── fib(2)
└── fib(3)
    ├── fib(2)
    └── fib(1)

随着 n 增大，重复计算会快速增加，时间复杂度接近指数级。

六、使用缓存优化递归

解决重复计算的常见方法是记忆化，将已经计算过的结果保存下来。

可以使用字典实现：

Python
运行
cache = {}

def fibonacci(n):
    if n <= 1:
        return n

    if n in cache:
        return cache[n]

    cache[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return cache[n]

Python 还提供了 functools.lru_cache：

Python
运行
from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n <= 1:
        return n

    return fibonacci(n - 1) + fibonacci(n - 2)

调用方式不变：

Python
运行
print(fibonacci(100))

缓存会显著减少重复递归调用，使时间复杂度从原始实现的指数级下降到近似线性级别。

对于具有大量重复子问题的递归算法，记忆化通常是一种非常有效的优化方式。

七、递归遍历文件目录

递归特别适合处理层级结构。

例如需要遍历一个目录及其所有子目录，可以使用 pathlib：

Python
运行
from pathlib import Path

def list_files(path):
    path = Path(path)

    for item in path.iterdir():
        if item.is_dir():
            list_files(item)
        else:
            print(item)

list_files("D:/project")

目录结构假设如下：


project
├── main.py
├── README.md
├── images
│   ├── logo.png
│   └── banner.jpg
└── src
    ├── app.py
    └── utils
        └── helper.py

递归函数可以自然地进入 images、src 和 utils 等子目录。

这种代码的优势在于，它与目录本身的树形结构高度匹配。

实际项目中还应该考虑权限异常、符号链接、超大目录以及路径安全等问题。

八、递归遍历树结构

树是递归算法最典型的应用场景之一。

假设定义一个简单的二叉树节点：

Python
运行
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

实现前序遍历：

Python
运行
def preorder(node):
    if node is None:
        return

    print(node.value)
    preorder(node.left)
    preorder(node.right)

如果树结构为：

执行：

Python
运行
preorder(root)

结果为：

原因在于每一个节点都可以被看作一棵更小的树：


树
├── 根节点
├── 左子树
└── 右子树

这种结构与递归天然匹配。

九、递归与分治思想

递归经常和分治算法结合使用。

分治的基本思想是：


原问题
   ↓
拆分成多个子问题
   ↓
递归解决子问题
   ↓
合并子问题结果
   ↓
得到最终结果

归并排序就是典型案例。

其核心过程是：


[8, 3, 5, 1]
       ↓
[8, 3] [5, 1]
   ↓       ↓
[8][3]   [5][1]
   ↓       ↓
 [3,8]   [1,5]
       ↓
   [1,3,5,8]

示例代码：

Python
运行
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2

    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

递归负责不断拆分数组，合并函数负责将两个有序数组重新组合。

归并排序平均和最坏情况下的时间复杂度为 O(n log n)，相比简单的递归遍历，更能体现递归与算法设计结合后的价值。

十、递归与循环有什么区别

很多递归问题同样可以通过循环解决。

例如计算累加：

Python
运行
def sum_loop(n):
    result = 0

    for i in range(1, n + 1):
        result += i

    return result

递归版本：

Python
运行
def sum_recursive(n):
    if n <= 0:
        return 0

    return n + sum_recursive(n - 1)

两者的主要区别在于：

对比项	递归	循环
代码结构	通常更简洁	通常更直接
调用栈	会占用调用栈	通常不会产生递归调用
深度限制	存在递归深度限制	通常没有此类限制
树形问题	非常适合	往往需要额外栈
调试难度	相对较高	通常较低
性能	可能存在函数调用开销	通常更高效

选择递归还是循环，不应该只看代码行数，而应该根据问题结构、数据规模和性能要求综合判断。

十一、Python递归函数常见问题

1. 缺少终止条件

下面的代码存在明显问题：

Python
运行
def test(n):
    print(n)
    test(n - 1)

调用：

Python
运行
test(5)

函数永远不会主动结束，最终会触发 RecursionError。

正确做法是增加明确的停止条件：

Python
运行
def test(n):
    if n <= 0:
        return

    print(n)
    test(n - 1)

2. 递归参数没有向终止条件靠近

例如：

Python
运行
def test(n):
    if n == 0:
        return

    test(n + 1)

即使存在终止条件，n 也在不断增大，所以永远无法达到 n == 0。

递归调用必须保证问题规模能够朝着终止条件不断收敛。

3. 重复计算导致性能下降

斐波那契数列就是典型例子。

如果一个递归函数反复计算相同的子问题，就应该考虑：

记忆化
动态规划
缓存
改写为循环

4. 递归层级过深

即使算法逻辑正确，也可能因为递归深度过大触发：


RecursionError: maximum recursion depth exceeded

这时不应该简单地把递归限制无限提高，而应该重新评估算法设计。

十二、Python递归函数的优化方法

递归优化通常可以从几个方向入手。

1. 缩小递归规模

递归调用应该尽可能快速地缩小问题规模。

例如：

Python
运行
return func(n - 1)

通常比一次只做很小变化、导致大量递归层级的设计更加容易控制。

2. 消除重复计算

对于存在重叠子问题的递归算法，可以使用缓存：

Python
运行
from functools import cache

@cache
def fib(n):
    if n <= 1:
        return n

    return fib(n - 1) + fib(n - 2)

cache 适合参数可哈希、且希望缓存全部计算结果的场景。

3. 必要时改成循环

例如简单的计数、累加、阶乘等问题，如果递归没有带来结构上的优势，循环通常更适合。

4. 使用显式栈替代递归

对于树和图的深度优先遍历，可以将系统调用栈改成自己维护的列表：

Python
运行
def preorder(root):
    if root is None:
        return

    stack = [root]

    while stack:
        node = stack.pop()
        print(node.value)

        if node.right:
            stack.append(node.right)

        if node.left:
            stack.append(node.left)

这样可以避免递归层级过深导致的问题。

5. 减少不必要的数据复制

递归处理列表时，如果每次都创建新的列表副本，可能产生额外的内存和时间开销。

例如：

Python
运行
arr[:mid]

会创建新的列表。

对于数据量较大的算法，可以考虑通过索引范围传递：

Python
运行
def process(arr, left, right):
    if left >= right:
        return

    mid = (left + right) // 2
    process(arr, left, mid)
    process(arr, mid + 1, right)

这种方式可以减少不必要的数据复制。

十三、如何判断一个问题适合递归

并不是看到“重复处理”就应该使用递归。

以下情况通常比较适合：

树形结构

例如：

二叉树遍历
文件目录遍历
XML/JSON嵌套结构处理
DOM节点遍历

分治算法

例如：

归并排序
快速排序
二分搜索的递归实现

回溯问题

例如：

全排列
组合
子集
迷宫搜索
N皇后问题

数学递推

例如：

阶乘
某些递推数列
最大公约数等问题

如果问题具有明显的层级结构或者可以自然地拆成相同类型的子问题，递归通常会让代码更加清晰。

十四、递归函数的调试技巧

递归调试最容易遇到的问题是“调用层级太多，不知道程序到底执行到哪里”。

可以临时打印参数：

Python
运行
def factorial(n):
    print("进入:", n)

    if n <= 1:
        return 1

    result = n * factorial(n - 1)

    print("返回:", n, result)
    return result

调用：

Python
运行
factorial(4)

通过观察“进入”和“返回”的顺序，就能直观看到递归调用栈的变化。

更复杂的递归还可以增加缩进：

Python
运行
def search(node, depth=0):
    if node is None:
        return

    print("  " * depth + str(node.value))

    search(node.left, depth + 1)
    search(node.right, depth + 1)

这样输出结果可以体现树的层级关系。

十五、递归算法复杂度分析

分析递归算法时，需要同时关注时间复杂度和空间复杂度。

例如：

Python
运行
def countdown(n):
    if n <= 0:
        return

    countdown(n - 1)

函数调用了 n 层，因此：


时间复杂度：O(n)
空间复杂度：O(n)

这里的空间复杂度主要来自递归调用栈。

再看一个二分查找的递归实现：

Python
运行
def binary_search(arr, target, left, right):
    if left > right:
        return -1

    mid = (left + right) // 2

    if arr[mid] == target:
        return mid

    if target < arr[mid]:
        return binary_search(arr, target, left, mid - 1)

    return binary_search(arr, target, mid + 1, right)