Почему этот код вызывает переполнение стека? И почему просто измените == 1 на <2, и тогда это сработает?

Question

Ниже приведен код рекурсивного Фибоначчи, и он вызывает переполнение стека. Почему простое изменение условия с n == 1 на n <2 заставляет его работать? </p>

Рассмотрим нормальную функцию Фибоначчи: F (n) = F (n - 1) + F (n - 2). Эта функция может быть представлена ​​здесь как F (n) = вычисления (n, 2).

Концепция здесь такова: вычислить (n, x) = вычислить (n - 1, x) + вычислить (n - 2, x) + вычислить (n - 3, x) + ... + вычислить (n - х, х);

    public static int calculate(int n, int x) {
        if (n == 1) {
            return n;
        }
        else {
            int output = 0;
            for (int i = 1; i <= x; i++) {
                output += calculate(n - i, x);
            }
            return output;
        }
    }
}

Answer 1

Когда ваше условие остановки равно n == 1, calculate не остановится, если вы передадите ему 0 или отрицательные значения, что вы и делаете в цикле.

Например, если n == 2 и x == 2, calculate(n - i, x) становится calculate(0,2), когда i == x.

Следовательно, if (n <= 1) или if (n < 2) является правильным условием остановки.