Python递归函数

递归是函数调用自身的编程技术，核心在于定义基准条件和递归条件。

递归基本结构

标准形式

def recursive_function(n):
    # 基准条件：终止递归
    if n <= 1:
        return 1
    # 递归条件：问题规模缩小
    return n * recursive_function(n - 1)

核心要素

1. 基准条件：终止递归的条件
2. 递归条件：调用自身并缩小问题规模

经典示例

阶乘计算

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))  # 120

斐波那契数列

def fibonacci(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))  # 55

遍历嵌套列表

def flatten_list(nested_list):
    result = []
    for item in nested_list:
        if isinstance(item, list):
            result.extend(flatten_list(item))
        else:
            result.append(item)
    return result

print(flatten_list([1, [2, 3], [4, [5, 6]]]))  # [1, 2, 3, 4, 5, 6]

递归深度限制

Python 默认递归深度限制为 1000 层。

查看限制

import sys
print(sys.getrecursionlimit())  # 1000

修改限制

import sys
sys.setrecursionlimit(2000)  # 设置为 2000

修改递归深度限制需谨慎，过深递归可能导致栈溢出。

无限递归后果

def infinite_recursion():
    return infinite_recursion()

infinite_recursion()  # RecursionError: maximum recursion depth exceeded

递归 vs 迭代

递归实现

def sum_recursive(n):
    if n <= 0:
        return 0
    return n + sum_recursive(n - 1)

迭代实现

def sum_iterative(n):
    result = 0
    for i in range(1, n + 1):
        result += i
    return result

迭代通常比递归效率更高，但递归代码更简洁直观。

递归优化

尾递归优化思路

# 非尾递归
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)  # 乘法在递归调用之后

# 尾递归形式（Python 不优化，但思想值得学习）
def factorial_tail(n, accumulator=1):
    if n <= 1:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)

Python 不支持尾递归优化，深度递归应考虑迭代替代。

要点总结

1. 递归必须包含基准条件和递归条件
2. 每次递归调用必须缩小问题规模
3. Python 默认递归深度限制 1000 层
4. 深度递归考虑使用迭代替代
5. 递归适合处理树形结构、分治问题