Python案例怎么实现函数递归？

wen python案例 2026-06-11 11

Python案例怎么实现函数递归？——5个经典案例带你掌握核心技巧

📖 目录导读

递归的本质：为什么需要递归？
递归的三要素：拆解问题、递归调用、终止条件
计算阶乘（入门级）
斐波那契数列（经典对比）
文件夹遍历（实用场景）
汉诺塔（思维进阶）
二分查找（性能优化）
常见错误与调试技巧
问答环节：递归 vs 循环怎么选？

递归的本质：为什么需要递归？

核心思想：把大问题拆解成结构相同、规模更小的子问题，直到子问题简单到可以直接解决，比如查词典时，遇到生词就查该生词的解释，而解释中又有生词，就继续查——直到查到所有词都认识为止。

Python案例怎么实现函数递归？

Python 中的递归，就是函数在自身内部调用自身，每一次调用，问题规模都在缩小，直到达到“基准情况”（base case）即停止条件。

递归的三要素（必须牢记）

要素	作用	反面案例
明确终止条件	防止无限递归导致栈溢出	忘记写 `if n == 0: return 1`
每次递归向终止推进	参数必须逐步逼近终止条件	`n-1` 写成 `n` 就会死循环
子问题与原问题结构一致	每次调用都是解决同类问题的“缩小版”	比如阶乘：`n! = n * (n-1)!`

案例一：计算阶乘（入门级）

问题描述

输入正整数 n，输出 n! = 1×2×3×…×n

递归实现

def factorial(n):
    # 终止条件（基准情况）
    if n == 1 or n == 0:
        return 1
    # 递归调用：n! = n * (n-1)!
    return n * factorial(n - 1)
print(factorial(5))  # 输出 120

执行过程图解（以 factorial(4) 为例）

factorial(4) → 4 * factorial(3)
               → 3 * factorial(2)
                   → 2 * factorial(1)
                       → 1
                   → 2 * 1 = 2
               → 3 * 2 = 6
           → 4 * 6 = 24

注意：每次递归调用都会在内存中开辟新的栈帧，深度过大（如超过1000层）会触发 RecursionError。

案例二：斐波那契数列（经典对比）

问题描述

斐波那契数列：0, 1, 1, 2, 3, 5, 8... 其规律是 F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)

朴素递归（性能差）

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)
print(fib(10))  # 输出55，但fib(40)会非常慢

问题：会重复计算大量子问题，时间复杂度 O(2^n)，例如计算 fib(5) 时 fib(3) 被计算了2次。

优化方法：记忆化递归

from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n-1) + fib_memo(n-2)

使用缓存后，时间复杂度降为 O(n)，空间复杂度 O(n)。

案例三：文件夹遍历（实用场景）

问题描述

遍历一个文件夹及其所有子文件夹，打印所有 .py 文件路径。

递归实现

import os
def list_py_files(root_dir):
    for item in os.listdir(root_dir):
        full_path = os.path.join(root_dir, item)
        if os.path.isfile(full_path) and item.endswith('.py'):
            print(full_path)
        elif os.path.isdir(full_path):
            # 递归遍历子文件夹
            list_py_files(full_path)
# 使用示例
list_py_files('.')

为什么适合递归？

文件夹结构天然是树形递归结构：每个文件夹都包含文件和子文件夹,子文件夹的结构和父文件夹完全一致。

案例四：汉诺塔（思维进阶）

问题描述

有三根柱子A、B、C，A上有n个大小不同的圆盘（小的在上大的在下），目标：将所有圆盘从A移到C，每次只能移动一个,且大盘不能压小盘。

递归思路

把 n-1 个盘从 A 移到 B（借助 C）
把第 n 个盘从 A 移到 C
把 n-1 个盘从 B 移到 C（借助 A）

实现代码

def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"移动圆盘1从 {source} 到 {target}")
        return
    # 递归：移动n-1个盘到辅助柱
    hanoi(n-1, source, auxiliary, target)
    # 移动最大盘
    print(f"移动圆盘{n}从 {source} 到 {target}")
    # 递归：移动n-1个盘从辅助柱到目标柱
    hanoi(n-1, auxiliary, target, source)
# 三个盘子时，需要7步
hanoi(3, 'A', 'C', 'B')

案例五：二分查找（性能优化）

问题描述

在有序数组中查找目标值，返回索引，传统循环写法已很高效，递归写法更体现“分治”思想。

def binary_search_recursive(arr, left, right, target):
    # 终止条件
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        # 在左半部分递归
        return binary_search_recursive(arr, left, mid-1, target)
    else:
        # 在右半部分递归
        return binary_search_recursive(arr, mid+1, right, target)
# 测试
sorted_list = [1, 3, 5, 7, 9, 11]
print(binary_search_recursive(sorted_list, 0, len(sorted_list)-1, 7))  # 输出3

常见错误与调试技巧

错误1：忘记终止条件

# 错误的阶乘
def bad_fact(n):
    return n * bad_fact(n-1)  # 没有判断n==0

运行会报 RecursionError: maximum recursion depth exceeded

错误2：终止条件无法到达

def infinite(n):
    if n == 100:
        return
    return infinite(n + 2)  # n从0开始，永远不会等于100

调试技巧

在递归函数开头添加 print(f"正在处理: {n}")，查看参数变化
使用 sys.getrecursionlimit() 查看当前递归深度限制（默认1000）
用 @lru_cache 装饰器检查是否有重复计算

问答环节：递归 vs 循环怎么选？

Q1：什么时候必须用递归？

A：当问题天然具有递归结构时，

树形结构遍历（文件夹、XML解析）
图算法（深度优先搜索）
分治算法（快速排序、归并排序）

Q2：递归和循环性能哪个好？

A：循环通常性能更好，因为递归有函数调用开销和栈空间消耗，但递归代码更简洁、可读性更高，对于斐波那契这种问题,记忆化递归可以消除性能差距。

Q3：Python递归深度限制是多少？怎么修改？

A：默认1000层，可通过 import sys; sys.setrecursionlimit(2000) 增大，但建议优先考虑用循环或尾递归优化（Python不支持自动尾递归优化）。

Q4：生产环境可以用递归吗？

A：可以,但需注意：

深度可控（如文件夹遍历通常不会超过几百层）
大数据量时优先循环
使用 try-except 捕获 RecursionError

递归就像一把瑞士军刀——在合适场景下用它能写出极简优雅的代码，但在错误场景（如超大规模数据处理）强行使用，可能带来栈溢出和性能问题，建议初学者先吃透阶乘和斐波那契这两个基础案例，再逐步挑战汉诺塔和实际项目中的树形结构处理。能写递归是一种能力，但知道何时不用递归更是一种智慧。