java 递归调用怎样避免重复计算

在 Java 中，为了避免递归调用中的重复计算，可以使用动态规划（Dynamic Programming）或者备忘录（Memoization）技术。这两种方法都可以将已经计算过的结果存储起来，以便在后续的递归调用中直接使用，从而减少计算量。

下面是两种方法的简要介绍和示例代码：

1. 动态规划（Dynamic Programming）

动态规划是一种将问题分解为子问题，并将子问题的解存储在一个表中，以便在后续计算中直接查找的方法。这种方法适用于具有重叠子问题和最优子结构的问题。

示例代码：

public int fibonacci(int n) {
    
    if (n <
= 1) {
    
        return n;

    }
    

    int[] dp = new int[n + 1];
    
    dp[0] = 0;
    
    dp[1] = 1;
    

    for (int i = 2;
     i <
    = n;
 i++) {
    
        dp[i] = dp[i - 1] + dp[i - 2];

    }
    

    return dp[n];

}

1. 备忘录（Memoization）

备忘录是一种将已经计算过的结果存储在一个数组或哈希表中的方法。在递归调用之前，先检查备忘录中是否已经存在该结果，如果存在则直接使用，否则进行计算并将结果存储在备忘录中。

示例代码：

public int fibonacci(int n) {
    
    if (n <
= 1) {
    
        return n;

    }
    

    int[] memo = new int[n + 1];
    
    return fibonacciHelper(n, memo);

}


private int fibonacciHelper(int n, int[] memo) {
    
    if (n <
= 1) {
    
        return n;

    }


    if (memo[n] == 0) {
    
        memo[n] = fibonacciHelper(n - 1, memo) + fibonacciHelper(n - 2, memo);

    }
    

    return memo[n];

}
    

这两种方法都可以有效地避免递归调用中的重复计算，从而提高程序的性能。

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！