java - 递归斐波那契方法的内存不是更快吗？

Question

我尝试内存递归斐波那契方法，它返回正确的数字。不过，看起来并没有比之前快多少。我假设这是因为我没有正确利用数组来跟踪，并且我仍在进行冗余调用。您能告诉我要更改什么以便我可以正确使用它吗？

不确定这是否重要，但 fibIndex[] 在全局区域中声明，并在获取输入后在 main 方法中设置为 [index + 1] 的长度。

public static BigInteger fibRec(int index)
{
    BigInteger results; 

    if (index <= 2)
    {
        results = BigInteger.ONE;
    }
    else
    {
        if (fibIndex[index] != null)
        {
            results = fibIndex[index];
        }
        else
        {
            results = fibRec(index - 1).add(fibRec(index - 2));

        }
    }
    return results;
}

Answer 1

它的运行速度并不快，因为您实际上没有使用内存，即您没有将结果放入数组中。如果您不这样做，那么您的实现实际上会变慢，因为您不断检查从未实际记住的已内存结果。这是您需要执行的操作。

public static BigInteger fibRec(int index) { 
    if (index <= 2) return BigInteger.ONE;

    BigInteger result = fibIndex[index];
    if (result == null) {
        result = fibRec(index - 1).add(fibRec(index - 2));
        fibIndex[index] = result; // you forgot this
    }
    return result;
}

编辑:我之前在这里做了一个注释，您不需要记住只调用一次的方法，但后来我记得该方法是递归的。所以忘记我之前所说的，内存实际上会大大加快该方法的速度。