Передача HashMap в рекурсивный метод не работает?

Question

Я объявляю HashMap для запоминания и передаю его в рекурсивный метод, но похоже, что HashMap на самом деле не хранит данные и не получает сброс при каждом рекурсивном вызове. Вот пример ниже:

    public static int fib(int n) {
        Map<Integer, Integer> memo = new HashMap<>();
        return fib(n, memo);
    }

    private static int fib(int n, Map<Integer, Integer> memo) {
        if (n < 0) {
            throw new IllegalArgumentException(
                "Index was negative. No such thing as a negative index in a series.");

        // base cases
        } else if (n == 0 || n == 1) {
            return n;
        }

        // see if we've already calculated this
        if (memo.containsKey(n)) {
            System.out.printf("grabbing memo[%d]\n", n);
            return memo.get(n);
        }

        System.out.printf("computing fib(%d)\n", n);
        int result = fib(n - 1) + fib(n - 2);

        // memoize
        memo.put(n, result);

        return result;
    }

вывод похож на ниже

computing fib(10)
computing fib(9)
computing fib(8)
computing fib(7)
computing fib(6)
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(3)
computing fib(2)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(3)
computing fib(2)
computing fib(6)
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(3)
computing fib(2)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(7)
computing fib(6)
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(3)
computing fib(2)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(3)
computing fib(2)
computing fib(8)
computing fib(7)
computing fib(6)
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(3)
computing fib(2)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(3)
computing fib(2)
computing fib(6)
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(3)
computing fib(2)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)

Но он работает нормально, если я использую HashMap в качестве переменной stati c и объявляю ее вне моей фиби () но это не то, что я хотел сделать. Кто-нибудь может мне помочь?

Спасибо.

Answer 1

Метод fib(int, Map) никогда не вызывается рекурсивно. Карта, которую вы создаете каждый раз, никогда не используется. Избавьтесь от fib(int) и замените звонками на fib(int, Map).

fib(n - 1, memo) + fib(n - 2, memo);