当前位置：首页 > article >正文

五大基础算法——递归算法

article 2025/3/17 11:02:39

递归算法 是一种通过函数调用自身来解决问题的算法思想。它将问题分解为规模更小的子问题，直到子问题可以直接解决，然后逐步合并子问题的解，最终得到原问题的解。以下是递归算法的核心概念、适用场景、实现方法及经典例题：

一、核心概念

递归定义
- 问题可以分解为规模更小的同类子问题。
基线条件（Base Case）
- 递归终止的条件，通常是问题规模最小的情况。
递归条件（Recursive Case）
- 将问题分解为更小的子问题，并调用自身解决。
递归栈
- 递归调用会使用栈来保存每一层的状态，可能导致栈溢出。

二、适用场景

数学问题
- 如阶乘、斐波那契数列、汉诺塔问题等。
数据结构操作
- 如树的遍历、图的搜索、链表的操作等。
分治算法
- 如归并排序、快速排序等。
组合问题
- 如全排列、子集生成等。

三、实现步骤

定义递归函数
- 明确函数的输入、输出和功能。
确定基线条件
- 找到问题的最小规模，直接返回结果。
分解问题
- 将问题分解为更小的子问题，调用自身解决。
合并结果
- 将子问题的解合并为原问题的解。

四、经典例题与代码

1. 阶乘计算

问题描述：计算n的阶乘（n!）。

def factorial(n):
    if n == 0:  # 基线条件
        return 1
    return n * factorial(n - 1)  # 递归条件

# 示例
print(factorial(5))  # 输出 120

2. 斐波那契数列

问题描述：计算第n个斐波那契数。

def fibonacci(n):
    if n <= 1:  # 基线条件
        return n
    return 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移动到B
        print(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 = val
        self.left = left
        self.right = right

def 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]