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

从汉诺塔到LeetCode掌握Python递归的5个经典刷题模板递归是算法设计中最优雅却也最令人困惑的概念之一。第一次接触递归的开发者往往会被它自我调用的特性所迷惑——一个函数怎么能调用自己呢但正是这种自我引用的特性让递归成为解决某些复杂问题的利器。在Python中递归函数的实现尤为简洁这使得它成为面试官钟爱的考察点也是LeetCode等算法平台上高频出现的解题模式。让我们从一个经典的例子开始汉诺塔问题。这个问题不仅展示了递归的思维方式还揭示了如何将复杂问题分解为相同结构的子问题。通过理解汉诺塔我们可以建立起递归思维的基础框架进而将其应用到阶乘计算、斐波那契数列、二叉树遍历等各类算法问题中。1. 理解递归从汉诺塔问题开始汉诺塔问题描述如下有三根柱子A、B、CA柱上有n个大小不一的圆盘大的在下小的在上。要求将所有圆盘从A柱移动到C柱移动过程中可以借助B柱但任何时候都不能将大盘放在小盘上面。1.1 递归思维分解解决汉诺塔问题的关键在于递归思维——将问题分解为更小的相同结构的子问题将A柱上的n-1个盘子移动到B柱借助C柱将A柱剩下的最大盘子直接移动到C柱将B柱上的n-1个盘子移动到C柱借助A柱这种分解方式体现了递归的核心思想将原问题转化为一个或多个规模更小的相同问题。def hanoi(n, source, auxiliary, target): if n 1: print(fMove disk 1 from {source} to {target}) return hanoi(n-1, source, target, auxiliary) print(fMove disk {n} from {source} to {target}) hanoi(n-1, auxiliary, source, target) # 示例移动3个盘子 hanoi(3, A, B, C)1.2 递归三要素每个递归函数都应包含三个关键要素基准条件Base Case递归终止的条件防止无限递归递归条件Recursive Case函数调用自身的条件问题规模缩小每次递归调用都应使问题规模更接近基准条件在汉诺塔的实现中基准条件是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)) # 输出: 1202.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 归并排序实现归并排序的递归过程将数组分成两半递归排序每一半合并两个已排序的子数组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(first0): 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 回溯算法框架回溯算法通常遵循以下模式选择做出一个选择约束检查选择是否满足约束条件目标检查是否达到目标状态回溯撤销选择尝试其他可能性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, val0, leftNone, rightNone): 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)) # 输出: 35.2 树形问题的递归模式树形问题的递归通常遵循以下模式处理空树情况基准条件递归处理左子树递归处理右子树合并左右子树的结果常见应用包括计算树的高度/深度遍历树前序、中序、后序判断树是否对称查找路径和等6. 递归模板五记忆化递归朴素递归可能导致重复计算记忆化技术通过存储已计算结果来优化性能。6.1 斐波那契数列的优化from functools import lru_cache lru_cache(maxsizeNone) def fibonacci(n): if n 2: return n return fibonacci(n-1) fibonacci(n-2) # 示例 print(fibonacci(100)) # 快速计算出3542248481792619150756.2 记忆化实现原理记忆化递归的实现通常有两种方式装饰器方式使用Python内置的lru_cache显式缓存手动维护一个字典存储计算结果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, acc1): 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, n1): result * i return result8. 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)) # 输出: olleh8.2 爬楼梯问题假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。有多少种不同的方法可以爬到楼顶lru_cache(maxsizeNone) 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)) # 输出: 898.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_count1, close_count) if close_count open_count: backtrack(current), open_count, close_count1) result [] backtrack(, 0, 0) return result # 示例 print(generate_parenthesis(3)) # 输出: [((())), (()()), (())(), ()(()), ()()()]9. 递归思维训练建议掌握递归需要刻意练习和正确的思维方式从小规模问题入手先理解基本情况如何工作相信递归假设假设更小规模的问题已经解决专注于当前步骤绘制递归树可视化递归调用过程关注三要素确保基准条件、递归条件和问题规模缩小都正确逐步增加复杂度从阶乘、斐波那契开始再到汉诺塔、树问题等递归不是编程的银弹但它是算法工具箱中不可或缺的利器。当面对一个复杂问题时不妨思考这个问题能否分解为更小的相同问题如果能递归可能就是你的最佳选择。