Фибоначчи с использованием рекурсивного метода дает мне переполнение стека

Question

public static int rFib(int n) {

    if(n == 0) {
        return 0;
    }

    if(n == 1) {
        return 1;
    }  

    return n + rFib(n-1);
}

Я пытаюсь найти наибольшее число, которое будет вычислено менее чем за 60 секунд.Затем я буду использовать итерационный метод для сравнения.Любое число больше 10 000 приводит к ошибке переполнения стека.Как мне избежать этого?

Answer 1

Одним из решений этой проблемы рекурсии является прерывание рекурсии с помощью динамического программирования.Например, памятка может быть применена и позволит вам реализовать ее как

private static Map<Integer, Integer> memo = new HashMap<>();
static {
    memo.put(0, 0);
    memo.put(1, 1);
}

public static int rFib(int n) {
    if (memo.containsKey(n)) {
        return memo.get(n);
    }
    int r = rFib(n - 2) + rFib(n - 1);
    memo.put(n, r);
    return r;
}

Answer 2

К сожалению, вы столкнулись с проблемой, которая является одновременно единственным наиболее часто используемым примером для понимания рекурсии и едва ли не единственным худшим приложением, к которому можно применить рекурсию.

Это действительно простопонять рекурсию из Фибоначчи, потому что это действительно тривиальный рекурсивный алгоритм, который вы можете кому-то объяснить и понять ... Что означает, что он отлично подходит для программирования рекурсии, верно?К сожалению, нет.

Я прошу прощения, если собираюсь рассказать вам то, что вы уже знаете, но я знаю, что Фибоначчи является одним из первых примеров во вводном программировании, поэтому я предполагаю, что это то, что вы собираетесьfrom.

В программировании есть такая вещь, как стек.Это буквально называется это, потому что это как стопка бумаг.Когда вы вызываете функцию, она помещает в стек всю информацию, необходимую для вызова функции, передачи аргументов и знания, как вернуться из функции (и некоторых других административных вещей).Когда эта функция рекурсивно вызывает себя, она помещает другой лист поверх стека .Затем эта функция помещает другой лист.Эти листы не удаляются до тех пор, пока функция не завершится ... Но поскольку одна функция не может завершить работу до завершения другой, она просто растет, растет и растет.

И стек только такой большой.Преднамеренно.Чтобы избежать этой проблемы.

Обычно рекурсия не используется для таких глубоких проблем. (Хвост-рекурсивные люди: игнорируйте это; если вы не знаете, что такое хвост-вызов-рекуссия: также игнорируйте это.)

Способ исправить это - несделай это.Общепризнанно, что почти в каждом приложении с произвольно рекурсивными функциями цикл for будет работать лучше (и быстрее).