Рекурсивные Фибоначчи в Java


Я только начал изучать рекурсию и мемоизация, поэтому я решил дать простую реализацию удар. Работает с некоторых простых случаях тест я придумал. Я могу что-нибудь добавить, чтобы сделать это более интересным? Я не уверен, если я могу изменить тип возвращаемого с дженерики как-то в зависимости от входного сигнала "Н" долго, типа BigInteger и т. д.

public static int fibonacci(int n) {
    if (n < 0) throw new IllegalArgumentException("n must be non-negative.");
    if (n == 0) return 0;
    if (n == 1) return 1;
    // if n >= 2
    Map<Integer, Integer> hm = new HashMap<Integer, Integer>(); // cache
    hm.put(0, 0);
    hm.put(1, 1);
    return fibHelper(n-1, hm) + fibHelper(n-2, hm);
}

static int fibHelper(int n, Map<Integer, Integer> hm) {
    if (hm.containsKey(n)) return hm.get(n);
    int fn = fibHelper(n-1, hm) + fibHelper(n-2, hm); // fn = fib of n
    hm.put(n, fn);
    return fn;
}


Комментарии
1 ответ

Вы пробовали запускать этот "большой" вход? Попробуйте его с fibonacci(10000) например. По крайней мере на моей машине по умолчанию это дает StackOverflowError.

Это потому, что Java не обрабатывает рекурсию хорошо. Так как вы собираетесь пересчитывать все значения при каждом вызове Фибоначчи(п)` вы могли бы также решить с помощью простого цикла for вместо.

public static int fibonacci(int n) {
if (n < 0) throw new IllegalArgumentException("n must be non-negative.");
if (n == 0) return 0;
if (n == 1) return 1;

int f1 = 0;
int f2 = 1;
for(int i = 2; i <= n; i++){
int temp = f2;
f2 += f1;
f1 = temp;
}
return f2;
}


Невозможно изменить тип возвращаемого динамически на основе значения во время выполнения. Видя, как числа Фибоначчи растут очень быстро, вы могли бы хотеть рассмотреть возвращение типа BigInteger по умолчанию. (Для Интс, вы не можете даже попасть в число 50).

public static BigInteger fibonacci(int n) {
if (n < 0) throw new IllegalArgumentException("n must be non-negative.");
if (n == 0) return BigInteger.ZERO;
if (n == 1) return BigInteger.ONE;

BigInteger f1 = BigInteger.ZERO;
BigInteger f2 = BigInteger.ONE;
for(int i = 2; i <= n; i++){
BigInteger temp = f2;
f2 = f2.add(f1);
f1 = temp;
}
return f2;
}

Лично я бы тоже не метод чисел Фибоначчи дальше, чем эти 2 темп veriables, чтобы отслеживать последние 2 значения. Если ваша программа предназначена для запроса числа Фибоначчи снова и снова, и вы готовы, чтобы получить немного скорости в обмен на некоторые памяти вы также можете предварительно рассчитать большое из этих чисел. Кроме обучающих целей, я не думаю, что это на самом деле стоит делать.

2
ответ дан 26 марта 2018 в 07:03 Источник Поделиться