递归算法

介绍

递归算法（Recursion Algorithm）是一种重要的编程方法，核心思想是函数通过调用自身来解决问题。在递归中，一个复杂的问题被分解为相同类型但规模更小的子问题，直到达到一个简单到可以直接解决的基本情况（基准情况）。递归算法特别适合解决具有自相似结构的问题，时间复杂度跟递归深度和每层处理的复杂度有关。

递归算法的妙处在于它能用简洁优雅的代码解决看似复杂的问题，但在使用时一定要注意避免无限递归和重复计算等问题。

算法步骤

定义递归函数，明确函数的功能和参数
确定递归的基准情况（终止条件）
将问题分解为更小的子问题
调用自身解决子问题
将子问题的结果组合起来，得到原问题的解

下图以阶乘为例，展示递归流程：

核心特性

自我调用：函数在其定义中直接或间接调用自身
终止条件：必须有基准情况使递归能够终止
问题分解：将大问题分解为相同类型但规模更小的子问题
时间复杂度：与递归深度和每层处理的工作量相关
空间复杂度：受函数调用栈深度影响，通常与递归深度成正比

基础实现

接下来通过阶乘（factorial）计算来展示递归算法的实现：

代码实现

Java实现

public class Factorial {
    public static int factorial(int n) {
        // 基准情况
        if (n == 0 || n == 1) {
            return 1;
        }
        
        // 递归情况：n! = n * (n-1)!
        return n * factorial(n - 1);
    }
    
    // 测试
    public static void main(String[] args) {
        for (int i = 0; i <= 10; i++) {
            System.out.printf("%d! = %d
", i, factorial(i));
        }
    }
}

在上述代码中，通过：

// 递归情况：n! = n * (n-1)!
return n * factorial(n - 1);

实现递归的核心思想，将计算 n! 的问题转化为计算 (n-1)! 的子问题。同时设置清晰的终止条件 if (n == 0 || n == 1) return 1; 确保递归能够结束。

def factorial(n):
    # 基准情况
    if n == 0 or n == 1:
        return 1
    
    # 递归情况
    return n * factorial(n - 1)

# 测试
for i in range(11):
    print(f"{i}! = {factorial(i)}")

优化策略

尾递归优化

通过将递归操作放在函数返回位置，可以被编译器优化，避免额外的栈空间消耗：

public static int factorialTailRecursive(int n) {
    return factorialHelper(n, 1);
}

private static int factorialHelper(int n, int accumulator) {
    // 基准情况
    if (n == 0 || n == 1) {
        return accumulator;
    }
    
    // 尾递归调用
    return factorialHelper(n - 1, n * accumulator);
}

记忆化递归

缓存已计算结果，避免重复计算：

public static int factorialMemoization(int n) {
    int[] memo = new int[n + 1];
    return factorialWithMemo(n, memo);
}

private static int factorialWithMemo(int n, int[] memo) {
    // 基准情况
    if (n == 0 || n == 1) {
        return 1;
    }
    
    // 检查是否已计算
    if (memo[n] != 0) {
        return memo[n];
    }
    
    // 计算并缓存结果
    memo[n] = n * factorialWithMemo(n - 1, memo);
    return memo[n];
}

优缺点

优点

代码简洁优雅，易于理解和实现
适合处理树、图等具有递归结构的数据
某些问题用递归比迭代更直观（比如树的遍历）

缺点

函数调用开销较大，会影响性能
递归深度过大时可能导致栈溢出
重复计算子问题可能导致指数级时间复杂度
调试和跟踪执行流程较为困难
资源消耗（特别是栈空间）随递归深度增加

应用场景

1）数学计算：阶乘、斐波那契数列、组合数等

2）数据结构操作：树的遍历、图的搜索（DFS）

3）分治算法：归并排序、快速排序

4）动态规划：子问题的递归求解

5）回溯算法：排列组合、八皇后、数独求解

扩展

斐波那契数列递归实现

▼

JavaJavaJava

复制代码

    `public static int fibonacci(int n) {     // 基准情况     if (n <= 1) {         return n;     }          // 递归情况：F(n) = F(n-1) + F(n-2)     return fibonacci(n - 1) + fibonacci(n - 2); }`

测验

这里准备了一些测试题，方便大家判断自己的掌握情况：

递归算法必须包含哪两个关键部分？为什么它们很重要？
尾递归与普通递归有什么区别？它有什么优势？

测验答案
递归算法必须包含基准情况（终止条件）和递归情况。基准情况确保递归能够终止，避免无限递归；递归情况将问题分解为更小的子问题。
尾递归是指递归调用是函数体中最后执行的操作。尾递归可以被编译器优化，通过重用当前栈帧降低空间复杂度，避免栈溢出。

E1 Recursion