跳到主要内容

Python 递归

什么是递归?

递归是一种编程技术,指的是函数调用自身的过程。换句话说,当一个函数在其定义中直接或间接地调用自己时,这种函数就被称为递归函数。

递归的核心思想可以概括为:把大问题分解成相似的小问题来解决

备注

递归在编程中非常重要,它可以让我们用简洁的代码解决复杂的问题,特别是那些具有分治特性的问题。

递归的基本结构

一个典型的递归函数包含两个主要部分:

  1. 基本情况(Base Case):当问题简单到可以直接解决时的情况,这是递归停止的条件。
  2. 递归情况(Recursive Case):将原问题分解为更小的子问题,并调用自身解决这些子问题。
python
def recursive_function(parameters):
# 基本情况
if base_case_condition:
return base_case_value

# 递归情况
return recursive_function(modified_parameters)

递归示例:阶乘计算

阶乘是递归的一个经典应用。n的阶乘(表示为n!)是指从1到n的所有整数的乘积。

数学定义

  • 0! = 1
  • n! = n × (n-1)!,当n > 0

Python 实现

python
def factorial(n):
# 基本情况
if n == 0 or n == 1:
return 1

# 递归情况
return n * factorial(n - 1)

# 测试阶乘函数
print(factorial(5)) # 输出: 120
print(factorial(0)) # 输出: 1

执行过程

以计算factorial(5)为例,我们可以看到递归的执行过程:

理解递归的关键点

1. 递归出口

每个递归函数必须有一个或多个基本情况(递归出口),否则函数将无限递归下去,最终导致栈溢出错误。

python
# 错误的递归(没有基本情况)
def bad_recursion(n):
return n * bad_recursion(n - 1) # 永远不会结束!

2. 递归深度

Python对递归深度有默认限制(通常为1000),以防止无限递归导致的栈溢出。可以通过sys.getrecursionlimit()查看当前限制:

python
import sys
print(sys.getrecursionlimit()) # 输出默认递归限制
警告

虽然可以通过sys.setrecursionlimit()增加递归深度限制,但这并不能真正解决问题,因为Python的递归本身就较为消耗资源。对于需要深度递归的问题,考虑使用迭代方法或尾递归优化更为合适。

3. 递归 vs 迭代

递归和迭代(循环)通常可以相互转换。以阶乘为例:

python
# 递归版本
def factorial_recursive(n):
if n == 0 or n == 1:
return 1
return n * factorial_recursive(n - 1)

# 迭代版本
def factorial_iterative(n):
result = 1
for i in range(1, n + 1):
result *= i
return result

比较

  • 递归版本通常代码更简洁,更直观地反映了问题的数学定义。
  • 迭代版本通常更高效,不会有栈溢出的风险。

经典递归案例

1. 斐波那契数列

斐波那契数列是另一个递归的经典应用:第1个和第2个数都是1,从第3个数开始,每个数都是前两个数的和。

python
def fibonacci(n):
# 基本情况
if n <= 0:
return 0
if n == 1 or n == 2:
return 1

# 递归情况
return fibonacci(n - 1) + fibonacci(n - 2)

# 测试
for i in range(1, 11):
print(f"fibonacci({i}) = {fibonacci(i)}")

输出:

fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = 2
fibonacci(4) = 3
fibonacci(5) = 5
fibonacci(6) = 8
fibonacci(7) = 13
fibonacci(8) = 21
fibonacci(9) = 34
fibonacci(10) = 55
提示

纯递归计算斐波那契数列效率很低,因为有大量重复计算。在实际应用中,建议使用动态规划或记忆化递归来优化。

2. 汉诺塔问题

汉诺塔是一个古老的数学问题:有三根柱子和多个大小不同的圆盘,开始时所有圆盘都叠在第一根柱子上,目标是将所有圆盘移动到第三根柱子上,并保持从小到大的顺序。移动过程中必须遵守以下规则:

  • 每次只能移动一个圆盘
  • 大圆盘不能放在小圆盘上面
python
def hanoi(n, source, auxiliary, target):
if n == 1:
print(f"把圆盘 1 从 {source} 移动到 {target}")
return

# 将n-1个圆盘从source移到auxiliary
hanoi(n - 1, source, target, auxiliary)

# 将第n个圆盘从source移到target
print(f"把圆盘 {n}{source} 移动到 {target}")

# 将n-1个圆盘从auxiliary移到target
hanoi(n - 1, auxiliary, source, target)

# 测试汉诺塔问题
hanoi(3, 'A', 'B', 'C')

输出:

把圆盘 1 从 A 移动到 C
把圆盘 2 从 A 移动到 B
把圆盘 1 从 C 移动到 B
把圆盘 3 从 A 移动到 C
把圆盘 1 从 B 移动到 A
把圆盘 2 从 B 移动到 C
把圆盘 1 从 A 移动到 C

递归的实际应用场景

除了上述经典案例,递归在实际编程中有很多应用:

1. 目录遍历

递归是遍历目录结构的自然方式:

python
import os

def list_files(directory):
"""递归列出目录中的所有文件"""
for item in os.listdir(directory):
path = os.path.join(directory, item)
if os.path.isfile(path):
print(f"文件: {path}")
elif os.path.isdir(path):
print(f"目录: {path}")
# 递归调用处理子目录
list_files(path)

# 使用示例
# list_files('/path/to/directory')

2. 数据结构操作

递归在操作树形数据结构(如二叉树)时非常有用:

python
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None

def inorder_traversal(node):
"""中序遍历二叉树"""
if node is None:
return

# 先遍历左子树
inorder_traversal(node.left)
# 访问当前节点
print(node.value)
# 再遍历右子树
inorder_traversal(node.right)

# 创建一个简单的二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# 中序遍历
inorder_traversal(root) # 输出: 4 2 5 1 3

3. 分治算法

递归是分治算法的核心,如归并排序:

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)

def merge(left, right):
"""合并两个已排序的数组"""
result = []
i = j = 0

while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1

result.extend(left[i:])
result.extend(right[j:])
return result

# 测试归并排序
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("排序结果:", sorted_arr) # 输出: [3, 9, 10, 27, 38, 43, 82]

递归优化技巧

1. 尾递归

尾递归是指递归调用是函数的最后一个操作的特殊情形,这种形式的递归可以被编译器或解释器优化。

python
# 普通递归版本的阶乘
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1) # 递归调用后还有乘法操作

# 尾递归版本的阶乘
def factorial_tail(n, accumulator=1):
if n == 0:
return accumulator
return factorial_tail(n - 1, n * accumulator) # 递归调用是最后操作
注意

虽然尾递归在理论上可以被优化,但Python解释器没有实现尾递归优化,因此在Python中尾递归和普通递归在性能上没有显著差异。

2. 记忆化递归

记忆化是一种优化技术,它通过存储已经计算过的结果来避免重复计算。

python
# 未优化的斐波那契数列计算
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)

# 使用记忆化的斐波那契数列计算
def fib_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]

# 使用Python内置的functools.lru_cache进行记忆化
from functools import lru_cache

@lru_cache(maxsize=None)
def fib_cached(n):
if n <= 1:
return n
return fib_cached(n-1) + fib_cached(n-2)

# 比较性能
import time

n = 35

start = time.time()
print(f"fib({n}) = {fib(n)}")
print(f"未优化用时: {time.time() - start:.2f}秒")

start = time.time()
print(f"fib_memo({n}) = {fib_memo(n)}")
print(f"记忆化优化用时: {time.time() - start:.2f}秒")

start = time.time()
print(f"fib_cached({n}) = {fib_cached(n)}")
print(f"lru_cache优化用时: {time.time() - start:.2f}秒")

总结

递归是一种强大的编程技术,它利用函数自我调用来解决问题。虽然递归可能不像迭代那样高效,但它往往能提供更为简洁和直观的解决方案,特别是对于本质具有递归性质的问题。

掌握递归需要理解:

  1. 基本情况(递归终止条件)
  2. 递归步骤(问题分解)
  3. 递归深度和效率考虑
  4. 何时使用递归,何时选择迭代

通过实践和不断练习,你将能够更自然地应用递归来解决各种编程挑战。

练习题

通过完成以下练习来提升你对递归的理解:

  1. 编写一个递归函数计算整数的幂(x^n)。
  2. 使用递归实现二分查找算法。
  3. 编写一个递归函数来判断字符串是否为回文。
  4. 实现递归版本的快速排序。
  5. 创建一个递归函数,计算给定数字的所有数字之和(例如,对于123,返回1+2+3=6)。

更多资源

祝你在递归学习中取得进步!递归学习的最佳方式就是:学习递归,然后递归地学习。🔄