Python 中的递归高级技术

摘要：递归是一个基本的编程概念，它涉及一个函数调用自身来一遍又一遍地解决较小的问题实例。对于可以分解为相同类型的子问题，它特别有用。说明递归的一个经典例子是斐波那契数列。

递归是一个基本的编程概念，它涉及一个函数调用自身来一遍又一遍地解决较小的问题实例。对于可以分解为相同类型的子问题，它特别有用。说明递归的一个经典例子是斐波那契数列。

基本上，当函数调用自身来执行任务时，就会发生递归。它通常涉及两个主要组成部分：

基本情况：

停止递归的条件。

递归大小写：

函数使用修改后的参数调用自身以减小问题大小的部分。

计算数字阶乘的简单递归函数示例：

def factorial(n): if n == 0: # Base case return 1 else: return n * factorial(n - 1) # Recursive caseprint(factorial(5)) # Output: 120

斐波那契数列是一系列数字，其中每个数字是前两个数字的总和。序列从 0 和 1 开始。在数学上，它可以定义为：

斐波那契（0） = 0斐波那契（1） = 1斐波那契（n） = 斐波那契（n-1） + 斐波那契（n-2）为 n > 1

序列开始如下：

0, 1, 1, 2, 3, 5, 8, 13, 21, …

在 Python 中实现斐波那契数列的一种简单方法是递归：

def fibonacci(n): if n == 0: # Base case return 0 elif n == 1: # Base case return 1 else: return fibonacci(n - 1) + fibonacci(n - 2) # Recursive case# Test the functionfor i in range(10): print(fibonacci(i), end=" ")

输出：

0 1 1 2 3 5 8 13 21 34

虽然这种实现简单易懂，但由于重复计算，对于较大的 n 值来说效率不高。

递归斐波那契实现具有明显的性能缺陷：

重叠子问题：

相同的斐波那契数数被多次计算。例如，要计算 fibonacci（5），该函数会计算 fibonacci（3）两次。递归斐波那契实现的时间复杂度为 O（2^n），这使得它对于大 n 来说是不切实际的。

记忆化是一种技术，它可以存储昂贵的函数调用的结果，并在再次出现相同的输入时重用它们。这可以显著提高递归解决方案的性能。

以下是使用记忆化的斐波那契函数的优化版本：

# Using a dictionary to store computed valuesdef fibonacci_memoized(n, memo={}): if n in memo: return memo[n] if n == 0: # Base case return 0 elif n == 1: # Base case return 1 else: memo[n] = fibonacci_memoized(n - 1, memo) + fibonacci_memoized(n - 2, memo) return memo[n]# Test the functionfor i in range(10): print(fibonacci_memoized(i), end=" ")

输出：

Memoization 将时间复杂度降低到 O（n），使函数更快、更高效。

Python 的 functools 模块提供了 @lru_cache 装饰器，可用于实现记忆化，而无需手动管理字典。它缓存函数调用的结果，并将其重复用于相同的输入。

以下是使用 @lru_cache 的斐波那契实现：

from functools import lru_cache@lru_cache(maxsize=None) # No limit on cache sizedef fibonacci_lru(n): if n == 0: # Base case return 0 elif n == 1: # Base case return 1 else: return fibonacci_lru(n - 1) + fibonacci_lru(n - 2) # Recursive case# Test the functionfor i in range(10): print(fibonacci_lru(i), end=" ")

输出：

使用 @lru_cache 可以简化代码，并提供与手动记忆相同的 O（n）时间复杂度。

递归经常用于树数据结构中以遍历节点。常见的树遍历方法包括 preorder、inorder 和 postorder 遍历。

下面是一个二叉树和中序遍历的递归实现的例子：

class Node: def __init__(self, value): self.value = value self.left = None self.right = Nonedef inorder_traversal(node): if node is not None: inorder_traversal(node.left) # Visit left subtree print(node.value, end=" ") # Visit node inorder_traversal(node.right) # Visit right subtree# Create a sample treeroot = Node(1)root.left = Node(2)root.right = Node(3)root.left.left = Node(4)root.left.right = Node(5)# Perform inorder traversalinorder_traversal(root)

输出：

4 2 5 1 3

在此示例中，递归通过自然地处理树的层次结构来简化遍历逻辑。

递归是一个强大的概念，它允许为涉及重复模式或分层结构的问题提供优雅的解决方案。虽然递归对于许多任务（例如计算斐波那契数或遍历树）来说既直观又直接，但递归可能会带来性能效率低下和堆栈溢出风险等限制。