递归函数Recursive Function是在函数内部直接或间接调用自身的函数其核心思想是将问题分解为更小的子问题直到达到终止条件基例。递归的本质是数学归纳法的编程实现。递归的三要素1.基例base Case递归的终止条件避免无限递归通常是问题的最简形式如n 0。2.递归步骤Recursive Step将问题分解为更小的子问题调用自身处理子问题。3.参数传递通过参数将问题规模逐步缩小经典递归示例1.阶乘函数Factorialdef factorial(n): # 基例0的阶乘是1 if n 0: return 1 # 递归步骤n! n × (n-1)! return n * factorial(n-1) print(factorial(5)) # 输出1205×4×3×2×12.斐波那契数列Fibonaccidef fibonacci(n): # 基例F(0)0, F(1)1 if n 1: return n # 递归步骤F(n) F(n-1) F(n-2) return fibonacci(n-1) fibonacci(n-2) print(fibonacci(6)) # 输出80,1,1,2,3,5,83.字符串反转def reverse_string(s): # 基例空字符串直接返回 if len(s) 0: return s # 递归步骤取最后一个字符 反转剩余部分 return s[-1] reverse_string(s[:-1]) print(reverse_string(hello)) # 输出olleh递归与迭代的对比特性递归迭代代码行数简洁无需循环通常较多需循环和状态管理空间复杂度高每次递归调用增加栈帧低仅需固定内存时间复杂度可能重复计算如斐波那契通常更优可读性直观问题天然递归结构需循环逻辑设计递归的常见应用场景1.树结构遍历前序/中序/后序遍历二叉树class TreeNode: def __init__(self, val, leftNone, rightNone): self.val val self.left left self.right right def inorder_traversal(root): if root: inorder_traversal(root.left) print(root.val) inorder_traversal(root.right)2.分治算法快速排序归并排序的递归实现3.数学问题幂运算如powxn x * powxn-14.动态规划记忆化递归优化用缓存存储中间结果递归的注意事项1.基例必须存在def infinite_recursion(): infinite_recursion() # 错误无基例导致栈溢出2.参数必须趋近基例def bad_factorial(n): if n 0: return 1 return bad_factorial(n1) # 错误参数不趋近基例3.栈溢出风险def deep_recursion(n): if n 0: return deep_recursion(n1) # 递归深度无限增长4.重复计算问题斐波那契递归实现中fib5会重复计算fib3fib2等解决方案使用记忆化递归Memoization。记忆化递归优化通过缓存中间结果避免重复计算from functools import lru_cache lru_cache(maxsizeNone) def fibonacci(n): if n 1: return n return fibonacci(n-1) fibonacci(n-2) print(fibonacci(30)) # 输出832040计算速度大幅提升
