递归斐波那契法的记忆化不是更快？

Question

我已经尝试递归斐波那契方法的记忆化，并返回正确的号码。但是，它不会出现任何比以前更快。我猜想，这是因为我没有利用阵列正确跟踪，我仍然在做重复的调用。能否请你告诉我什么改变，所以我可以正确地使用它？

不知道它的问题，但fibIndex[]在全球范围申报，并获取输入后设置在主方法中的[索引+ 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

因为你没有实际使用记忆化数组中，即你是不是把结果它没有运行速度更快。如果你不这样做，那么您的实现实际上是比较慢的，因为你不断检查，你从来没有真正memoized memoized结果。下面是你需要做的事。

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;
}

编辑：我早一点你不需要给你打电话只是一次方法的memoization做了说明，但后来我想起，该方法是递归的。所以忘了我以前在这里说，记忆化实际上会加速方法颇多。

Answer 2

我注意到您实际上并不在fibIndex填充任何地方。在此基础上，如果将你的if语句的条件触发？

这是否给你什么来解决一个有意义吗？