Python递归算法案例如何实现递归

wen python案例 2026-06-30 214

本文目录导读：

Python递归算法案例如何实现递归

什么是递归
经典递归案例
递归的优缺点
优化技巧
递归的调试技巧
实践建议

我来详细介绍Python递归算法的实现方法和经典案例。

什么是递归

递归是一种函数调用自身的编程技巧,包含两个核心要素：

递归基（终止条件）：停止递归的条件
递归步骤：将问题分解为更小规模的同类问题

经典递归案例

阶乘计算

def factorial(n):
    """
    计算n的阶乘
    终止条件：n <= 1时返回1
    递归步骤：n * factorial(n-1)
    """
    # 递归基
    if n <= 1:
        return 1
    # 递归步骤
    return n * factorial(n - 1)
# 测试
print(factorial(5))  # 输出: 120 (5*4*3*2*1)

斐波那契数列

def fibonacci(n):
    """
    计算斐波那契数列第n项
    终止条件：n <= 1时返回n
    递归步骤：fibonacci(n-1) + fibonacci(n-2)
    """
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)
# 测试
for i in range(10):
    print(fibonacci(i), end=" ")  # 输出: 0 1 1 2 3 5 8 13 21 34

汉诺塔问题

def hanoi(n, source, target, auxiliary):
    """
    汉诺塔问题
    n: 盘子数量
    source: 源柱子
    target: 目标柱子
    auxiliary: 辅助柱子
    """
    if n == 1:
        print(f"将盘子1从{source}移动到{target}")
        return
    # 将n-1个盘子从source移动到auxiliary
    hanoi(n - 1, source, auxiliary, target)
    # 将最大的盘子移动到target
    print(f"将盘子{n}从{source}移动到{target}")
    # 将n-1个盘子从auxiliary移动到target
    hanoi(n - 1, auxiliary, target, source)
# 测试
hanoi(3, 'A', 'C', 'B')

二叉树遍历

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
def inorder_traversal(root):
    """
    二叉树中序遍历
    """
    if root is None:
        return []
    result = []
    # 遍历左子树
    result.extend(inorder_traversal(root.left))
    # 访问根节点
    result.append(root.value)
    # 遍历右子树
    result.extend(inorder_traversal(root.right))
    return result
# 创建测试二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(inorder_traversal(root))  # 输出: [4, 2, 5, 1, 3]

快速排序

def quick_sort(arr):
    """
    快速排序递归实现
    """
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]
    return quick_sort(less) + [pivot] + quick_sort(greater)
# 测试
arr = [3, 6, 8, 10, 1, 2, 1]
print(quick_sort(arr))  # 输出: [1, 1, 2, 3, 6, 8, 10]

文件目录遍历

import os
def list_files(path, indent=0):
    """
    递归遍历文件目录
    """
    items = os.listdir(path)
    for item in items:
        full_path = os.path.join(path, item)
        if os.path.isdir(full_path):
            print(" " * indent + f"📁 {item}/")
            list_files(full_path, indent + 2)
        else:
            print(" " * indent + f"📄 {item}")
# 测试（请确保路径存在）
# list_files(".")

递归的优缺点

优点

代码简洁：表达逻辑清晰
易于理解：符合数学归纳思维
处理树形结构：天生适合处理递归定义的数据结构

缺点

性能开销：函数调用有额外开销
栈溢出风险：递归深度过大可能导致栈溢出
重复计算：如朴素斐波那契有大量重复计算

优化技巧

尾递归优化

def factorial_tail(n, accumulator=1):
    """
    尾递归优化的阶乘
    """
    if n <= 1:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)
# Python默认不支持尾递归优化，但这是一个好的编程习惯

记忆化递归

from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci_memo(n):
    """
    使用缓存优化的斐波那契
    """
    if n <= 1:
        return n
    return fibonacci_memo(n - 1) + fibonacci_memo(n - 2)
# 测试
print(fibonacci_memo(100))  # 快速计算

递归的调试技巧

def factorial_debug(n, depth=0):
    """带调试信息的阶乘"""
    indent = "  " * depth
    print(f"{indent}factorial({n}) 被调用")
    if n <= 1:
        print(f"{indent}返回 1")
        return 1
    result = n * factorial_debug(n - 1, depth + 1)
    print(f"{indent}返回 {result}")
    return result
# 测试
factorial_debug(5)