根据斐波那契递归函数创建记忆算法

Question

对于学校作业，我们必须创建一个记忆的fibonacci函数，该函数可重用计算fibonacci的递归实现。

设计记忆功能以使其利用现有功能的好方法是什么？到目前为止，这是我的实现：

基类：

    public int computeFibonacci(int position) {
        assertPosition(position);

        if (position < 2) {
            return 1;
        }
        return computeFibonacci(position - 1) + computeFibonacci(position - 2);
    }

继承的类：

    public int computeFibonacci(int position) {
        assertPosition(position);

        if (position < 2) {
            return 1;
        }

        if (this.memoizedList.containsKey(position)) {
            return this.memoizedList.get(position);
        }
        int result = super.computeFibonacci(position - 1) + super.computeFibonacci(position - 2);
        this.memoizedList.put(position, result);
        return result;
    }

Answer 1

您的子类版本未充分利用缓存的值。例如，如果您调用computeFibonacci(5)，并且memoizedList不包含该键，则即使它们已经被缓存，您也将调用super.computeFibonacci(4)和super.computeFibonacci(3)。相反，您应该致电super.computeFibonacci(5)。

public int computeFibonacci(int position) {
    assertPosition(position);

    if (position < 2) {
        return 1;
    }

    if (this.memoizedList.containsKey(position)) {
        return this.memoizedList.get(position);
    } else {
        int result = super.computeFibonacci(position);
        this.memoizedList.put(position, result);
        return result;
    }
}

Answer 2

关于在基类中重用递归实现存在困惑。如果调用递归实现，它将递归计算fib（n-1）+ fib（n-2）= ...，这与备忘功能冲突。备忘功能试图节省计算时间。备忘：

public int computeFibonacci(int position) {
        assertPosition(position);

        if (position < 2) {
            return 1;
        }

        if (this.memoizedList.containsKey(position)) {
            return this.memoizedList.get(position);
        }
        int result = computeFibonacci(position - 1) + computeFibonacci(position - 2);
        this.memoizedList.put(position, result);
        return result;
    }

例如，您尝试打印斐波纳契中的前1000个元素，备忘录功能将为计算出的元素节省时间。