从汉诺塔到LeetCode：掌握Python递归的5个经典刷题模板（含阶乘、斐波那契）

从汉诺塔到LeetCode：掌握Python递归的5个经典刷题模板

递归是算法设计中最优雅却也最令人困惑的概念之一。第一次接触递归的开发者往往会被它自我调用的特性所迷惑——一个函数怎么能调用自己呢？但正是这种自我引用的特性，让递归成为解决某些复杂问题的利器。在Python中，递归函数的实现尤为简洁，这使得它成为面试官钟爱的考察点，也是LeetCode等算法平台上高频出现的解题模式。

让我们从一个经典的例子开始：汉诺塔问题。这个问题不仅展示了递归的思维方式，还揭示了如何将复杂问题分解为相同结构的子问题。通过理解汉诺塔，我们可以建立起递归思维的基础框架，进而将其应用到阶乘计算、斐波那契数列、二叉树遍历等各类算法问题中。

1. 理解递归：从汉诺塔问题开始

汉诺塔问题描述如下：有三根柱子A、B、C，A柱上有n个大小不一的圆盘，大的在下，小的在上。要求将所有圆盘从A柱移动到C柱，移动过程中可以借助B柱，但任何时候都不能将大盘放在小盘上面。

1.1 递归思维分解

解决汉诺塔问题的关键在于递归思维——将问题分解为更小的相同结构的子问题：

1. 将A柱上的n-1个盘子移动到B柱（借助C柱）
2. 将A柱剩下的最大盘子直接移动到C柱
3. 将B柱上的n-1个盘子移动到C柱（借助A柱）

这种分解方式体现了递归的核心思想：将原问题转化为一个或多个规模更小的相同问题。

def hanoi(n, source, auxiliary, target): if n == 1: print(f"Move disk 1 from {source} to {target}") return hanoi(n-1, source, target, auxiliary) print(f"Move disk {n} from {source} to {target}") hanoi(n-1, auxiliary, source, target) # 示例：移动3个盘子 hanoi(3, 'A', 'B', 'C')

1.2 递归三要素

每个递归函数都应包含三个关键要素：

1. 基准条件（Base Case）：递归终止的条件，防止无限递归
2. 递归条件（Recursive Case）：函数调用自身的条件
3. 问题规模缩小：每次递归调用都应使问题规模更接近基准条件

在汉诺塔的实现中：

• 基准条件是n == 1
• 递归条件是n > 1
• 问题规模通过n-1不断缩小

2. 递归模板一：简单数学计算

递归非常适合解决可以数学归纳法定义的问题，如阶乘和斐波那契数列。

2.1 阶乘计算

阶乘的递归定义：

• 0! = 1（基准条件）
• n! = n × (n-1)!（递归条件）

def factorial(n): if n == 0: # 基准条件 return 1 return n * factorial(n-1) # 递归调用 # 示例 print(factorial(5)) # 输出: 120

2.2 斐波那契数列

斐波那契数列定义：

• F(0) = 0, F(1) = 1（基准条件）
• F(n) = F(n-1) + F(n-2)（递归条件）

def fibonacci(n): if n == 0: return 0 if n == 1: return 1 return fibonacci(n-1) + fibonacci(n-2) # 示例 print(fibonacci(10)) # 输出: 55

注意：这种朴素递归实现斐波那契数列效率很低，时间复杂度为O(2^n)。实际应用中应使用记忆化递归或迭代法优化。

3. 递归模板二：分治策略

分治（Divide and Conquer）是递归的重要应用，将问题分解为多个子问题，分别解决后再合并结果。典型的应用包括归并排序和快速排序。

3.1 归并排序实现

归并排序的递归过程：

1. 将数组分成两半
2. 递归排序每一半
3. 合并两个已排序的子数组

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 # 示例 print(merge_sort([38, 27, 43, 3, 9, 82, 10]))

3.2 分治问题特征

适合分治策略的问题通常具有以下特征：

• 问题可以分解为多个相同或相似的子问题
• 子问题的解可以合并为原问题的解
• 子问题相互独立，不重叠（重叠时更适合动态规划）

4. 递归模板三：回溯算法

回溯是一种通过尝试所有可能性来解决问题的算法，当发现当前路径不能得到解时，就"回溯"到上一步尝试其他选择。

4.1 全排列问题

给定一个不含重复数字的数组，返回所有可能的排列。

def permute(nums): def backtrack(first=0): if first == n: # 基准条件：所有位置都已填满 output.append(nums[:]) for i in range(first, n): nums[first], nums[i] = nums[i], nums[first] # 交换 backtrack(first + 1) # 递归填下一个位置 nums[first], nums[i] = nums[i], nums[first] # 撤销交换 n = len(nums) output = [] backtrack() return output # 示例 print(permute([1, 2, 3]))

4.2 回溯算法框架

回溯算法通常遵循以下模式：

1. 选择：做出一个选择
2. 约束：检查选择是否满足约束条件
3. 目标：检查是否达到目标状态
4. 回溯：撤销选择，尝试其他可能性

def backtrack(candidate): if find_solution(candidate): output.append(candidate) return for next_candidate in list_of_candidates: if is_valid(next_candidate): make_move(next_candidate) backtrack(next_candidate) undo_move(next_candidate)

5. 递归模板四：树形问题

许多树形问题天然适合递归解决，因为树本身就是递归定义的数据结构。

5.1 二叉树的最大深度

class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def max_depth(root): if not root: # 基准条件：空树深度为0 return 0 left_depth = max_depth(root.left) # 递归求左子树深度 right_depth = max_depth(root.right) # 递归求右子树深度 return max(left_depth, right_depth) + 1 # 当前节点深度 # 示例 root = TreeNode(3) root.left = TreeNode(9) root.right = TreeNode(20) root.right.left = TreeNode(15) root.right.right = TreeNode(7) print(max_depth(root)) # 输出: 3

5.2 树形问题的递归模式

树形问题的递归通常遵循以下模式：

1. 处理空树情况（基准条件）
2. 递归处理左子树
3. 递归处理右子树
4. 合并左右子树的结果

常见应用包括：

• 计算树的高度/深度
• 遍历树（前序、中序、后序）
• 判断树是否对称
• 查找路径和等

6. 递归模板五：记忆化递归

朴素递归可能导致重复计算，记忆化技术通过存储已计算结果来优化性能。

6.1 斐波那契数列的优化

from functools import lru_cache @lru_cache(maxsize=None) def fibonacci(n): if n < 2: return n return fibonacci(n-1) + fibonacci(n-2) # 示例 print(fibonacci(100)) # 快速计算出354224848179261915075

6.2 记忆化实现原理

记忆化递归的实现通常有两种方式：

1. 装饰器方式：使用Python内置的lru_cache
2. 显式缓存：手动维护一个字典存储计算结果

def memo_fibonacci(n, memo={}): if n in memo: return memo[n] if n < 2: return n memo[n] = memo_fibonacci(n-1, memo) + memo_fibonacci(n-2, memo) return memo[n]

6.3 何时使用记忆化

考虑使用记忆化优化当递归问题具有以下特征：

• 存在大量重复子问题
• 子问题的解可以被缓存和重用
• 问题具有最优子结构性质

7. 递归的陷阱与优化

虽然递归代码简洁优雅，但使用不当可能导致严重问题。

7.1 常见陷阱

7.2 尾递归优化

尾递归是指递归调用是函数的最后一步操作。某些语言/编译器能优化尾递归，避免栈溢出。

def factorial(n, acc=1): if n == 0: return acc return factorial(n-1, acc*n) # 尾递归形式

注意：Python解释器并不支持尾递归优化，这里仅为展示概念。在实际Python代码中，深度递归问题应考虑改用迭代实现。

7.3 递归转迭代

任何递归算法都可以转换为迭代形式，通常使用栈来模拟调用栈。

def factorial_iter(n): result = 1 for i in range(1, n+1): result *= i return result

8. LeetCode实战：递归问题精选

让我们用几个LeetCode经典题目来巩固递归的应用。

8.1 反转字符串

编写一个函数，将输入的字符串反转。

def reverse_string(s): if len(s) <= 1: return s return reverse_string(s[1:]) + s[0] # 示例 print(reverse_string("hello")) # 输出: "olleh"

8.2 爬楼梯问题

假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。有多少种不同的方法可以爬到楼顶？

@lru_cache(maxsize=None) def climb_stairs(n): if n == 1: return 1 if n == 2: return 2 return climb_stairs(n-1) + climb_stairs(n-2) # 示例 print(climb_stairs(10)) # 输出: 89

8.3 括号生成

数字n代表生成括号的对数，设计函数生成所有可能的有效括号组合。

def generate_parenthesis(n): def backtrack(current, open_count, close_count): if len(current) == 2*n: result.append(current) return if open_count < n: backtrack(current+"(", open_count+1, close_count) if close_count < open_count: backtrack(current+")", open_count, close_count+1) result = [] backtrack("", 0, 0) return result # 示例 print(generate_parenthesis(3)) # 输出: ['((()))', '(()())', '(())()', '()(())', '()()()']

9. 递归思维训练建议

掌握递归需要刻意练习和正确的思维方式：

1. 从小规模问题入手：先理解基本情况如何工作
2. 相信递归假设：假设更小规模的问题已经解决，专注于当前步骤
3. 绘制递归树：可视化递归调用过程
4. 关注三要素：确保基准条件、递归条件和问题规模缩小都正确
5. 逐步增加复杂度：从阶乘、斐波那契开始，再到汉诺塔、树问题等

递归不是编程的银弹，但它是算法工具箱中不可或缺的利器。当面对一个复杂问题时，不妨思考：这个问题能否分解为更小的相同问题？如果能，递归可能就是你的最佳选择。