递归算法 是一种通过函数调用自身来解决问题的算法思想。它将问题分解为规模更小的子问题，直到子问题可以直接解决，然后逐步合并子问题的解，最终得到原问题的解。以下是递归算法的核心概念、适用场景、实现方法及经典例题：
一、核心概念
- 递归定义
- 问题可以分解为规模更小的同类子问题。
- 基线条件（Base Case）
- 递归终止的条件，通常是问题规模最小的情况。
- 递归条件（Recursive Case）
- 将问题分解为更小的子问题，并调用自身解决。
- 递归栈
- 递归调用会使用栈来保存每一层的状态，可能导致栈溢出。
二、适用场景
- 数学问题
- 如阶乘、斐波那契数列、汉诺塔问题等。
- 数据结构操作
- 如树的遍历、图的搜索、链表的操作等。
- 分治算法
- 如归并排序、快速排序等。
- 组合问题
- 如全排列、子集生成等。
三、实现步骤
- 定义递归函数
- 明确函数的输入、输出和功能。
- 确定基线条件
- 找到问题的最小规模，直接返回结果。
- 分解问题
- 将问题分解为更小的子问题，调用自身解决。
- 合并结果
- 将子问题的解合并为原问题的解。
四、经典例题与代码
1. 阶乘计算
问题描述：计算n的阶乘（n!）。
def factorial(n):if n == 0: # 基线条件return 1return n * factorial(n - 1) # 递归条件# 示例
print(factorial(5)) # 输出 120
2. 斐波那契数列
问题描述：计算第n个斐波那契数。
def fibonacci(n):if n <= 1: # 基线条件return nreturn fibonacci(n - 1) + fibonacci(n - 2) # 递归条件# 示例
print(fibonacci(6)) # 输出 8
3. 汉诺塔问题
问题描述：将n个盘子从A柱移动到C柱，借助B柱，且每次只能移动一个盘子，大盘子不能放在小盘子上。
def hanoi(n, source, target, auxiliary):if n == 1: # 基线条件print(f"Move disk 1 from {source} to {target}")else:hanoi(n - 1, source, auxiliary, target) # 将n-1个盘子从A移动到Bprint(f"Move disk {n} from {source} to {target}")hanoi(n - 1, auxiliary, target, source) # 将n-1个盘子从B移动到C# 示例
hanoi(3, 'A', 'C', 'B')
4. 二叉树遍历
问题描述：递归实现二叉树的前序遍历。
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef preorderTraversal(root):if not root: # 基线条件return []return [root.val] + preorderTraversal(root.left) + preorderTraversal(root.right)# 示例
root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
print(preorderTraversal(root)) # 输出 [1, 2, 3]
五、递归算法的优缺点
优点
- 代码简洁
- 递归代码通常比迭代代码更简洁易懂。
- 问题分解清晰
- 递归天然适合分治思想，问题分解直观。
- 适合树和图结构
- 递归非常适合处理树和图的遍历问题。
缺点
- 栈溢出风险
- 递归深度过大时，可能导致栈溢出。
- 效率较低
- 递归调用有额外开销，且可能重复计算（如斐波那契数列）。
- 难以调试
- 递归调用层次较深时，调试困难。
六、优化递归算法
- 尾递归优化
- 将递归调用放在函数最后，编译器可以优化为迭代。
- 记忆化（Memoization）
- 缓存已计算的子问题结果，避免重复计算。
- 迭代替代递归
- 使用栈或循环结构实现递归逻辑。
七、适用问题特征
- 问题可以分解为同类子问题。
- 子问题的解可以合并为原问题的解。
- 常见问题包括：数学问题、树和图遍历、分治算法等。
递归算法是一种强大的工具，适合解决分治和回溯类问题。在实际应用中，需注意递归深度和效率问题，必要时进行优化或改用迭代实现。