Создание алгоритма запоминания с учетом рекурсивной функции Фибоначчи

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

Существует путаница в отношении повторного использования рекурсивной реализации в базовом классе. Если вы вызываете рекурсивную реализацию, она будет рекурсивно вычислять fib (n) = fib (n-1) + fib (n-2) = ..., что противоречит функции memo. Функция Memo пытается сэкономить время для рассчитанных. Для памятки:

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 элементов в Фибоначчи, функция памятки сэкономит время на вычисленных.

Answer 2

Ваша версия подкласса не в полной мере использует кэшированные значения. Например, если вы вызываете 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;
    }
}