Рекурсия против итерации (последовательность Фибоначчи)

Ответ 1

Для краткости пусть F (x) - рекурсивный Фибоначчи

F(10) = F(9)                      + F(8)
F(10) = F(8)        + F(7)        + F(7) + F(6)
F(10) = F(7) + F(6) + F(6) + F(5) + 4 more calls.
....

Итак, вы дважды вызываете F (8) F (7) 3 раза, F (6) 5 раз, F (5) 7 раз.. и т.д.

Таким образом, с большими входами дерево становится все больше и больше.

Ответ 2

В этой статье проводится сравнение между рекурсией и итерацией и распространяется их приложение на генерирование чисел фибоначчи.

Как отмечено в статье,

Причиной плохой производительности является тяжелый толчок регистров на плохом уровне каждого рекурсивного вызова.

который в основном говорит, что в рекурсивном методе больше накладных расходов.

Кроме того, посмотрите Memoization

Ответ 3

При выполнении рекурсивной реализации алгоритма фибоначчи вы добавляете избыточные вызовы, повторяя одни и те же значения снова и снова.

fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)

Обратите внимание, что fib(2) будет избыточно рассчитан как для fib(4), так и для fib(3). Однако это можно преодолеть с помощью метода Memoization, что улучшает эффективность рекурсивной фибоначчи, сохраняя значения, которые вы вычислили один раз. Дальнейшие вызовы fib(x) для известных значений могут быть заменены простым поиском, устраняя необходимость в дальнейших рекурсивных вызовах.

Это основное отличие между итеративным и рекурсивным подходами, если вам интересно, есть и другие, более эффективные алгоритмы вычисления фибоначчи числа.

Ответ 4

Используя рекурсию, как у вас есть, сложность времени O(fib(n)), что очень дорого. Итеративный метод O(n) Это не показывает, потому что: а) ваши тесты очень короткие, код даже не компилируется. B) вы использовали очень маленькие цифры.

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

Ответ 5

Почему рекурсия медленнее?

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

Кроме того, в рекурсии сегмент стека создается во время выполнения. Компилятор не знает , сколько памяти будет занято.

Вот почему, если вы не можете правильно обработать свой Базовый регистр, вы претерпите известную ошибку с именем StackOverflow:).

Ответ 6

Если кому-то интересна итеративная функция с массивом:

public static void fibonacci(int y)
{
    int[] a = new int[y+1];
    a[0] = 0;
    a[1] = 1;
    System.out.println("Step 0: 0");
    System.out.println("Step 1: 1");
    for(int i=2; i<=y; i++){
        a[i] = a[i-1] + a[i-2];
        System.out.println("Step "+i+": "+a[i]);
    }
    System.out.println("Array size --> "+a.length);
}

Это решение аварийно завершает входное значение 0.

Причина: массив a будет инициализирован 0+1=1, но последовательное присвоение a[1] приведет к исключению индекса из пределов.

Либо добавьте оператор if, возвращающий 0 на y=0, либо инициализируя массив y+2, который будет тратить 1 int, но все равно будет иметь постоянное пространство и не изменять большой O.

Ответ 7

Рекурсивный подход, который вы используете, неэффективен. Я бы предложил использовать хвостовую рекурсию. В отличие от вашего подхода хвостовая рекурсия сохраняет только один вызов функции в стеке в любой момент времени.

public static int tailFib(int n) {
    if (n <= 1) {
        return n;
    }
    return tailFib(0, 1, n);
}

private static int tailFib(int a, int b, int count) {
    if(count <= 0) {
        return a;
    }
    return tailFib(b, a+b, count-1);
}

public static void main(String[] args)  throws Exception{
    for (int i = 0; i <10; i++){
        System.out.println(tailFib(i));
    }
}

Ответ 8

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

private static final double GOLDEN_NUMBER = 1.618d;

public long fibonacci(int n) {
    double sqrt = Math.sqrt(5);

    double result = Math.pow(GOLDEN_NUMBER, n);

    result = result - Math.pow(1d - GOLDEN_NUMBER, n);

    result = Math.round(result / sqrt);

    return Double.valueOf(result).longValue();
}

Ответ 9

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

Оцените сложность времени на бумаге в терминах O (что-то).

Сравнивая вышеупомянутые два подхода, временная сложность итеративного подхода равна O (n), тогда как для рекурсивного подхода O (2 ^ n).

Попробуйте найти временную сложность fib(4)

Итеративный подход, цикл оценивается 4 раза, поэтому его временная сложность O(n).

Рекурсивный подход,

                               fib(4)

             fib(3)              +               fib(2)

      fib(2)   +    fib(1)           fib(1)     +       fib(0)

fib(1)  +  fib(0)

поэтому fib() вызывается 9 раз, что немного меньше 2 ^ n, когда значение n велико и даже мало (помните, что BigOh (O) заботится о upper bound).

В результате мы можем сказать, что итеративный подход оценивается в polynomial time, тогда как рекурсивный оценивается в exponential time

Ответ 10

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

public static int fibonacci(int n) {

        if(n <=  0) return 0;
        if(n == 1) return 1;

        int[] arr = new int[n+1];

        // this is faster than using Array
        // List<Integer> lis = new ArrayList<>(Collections.nCopies(n+1, 0));

        arr[0] = 0;
        arr[1] = 1; 

        return fiboHelper(n, arr);
    }

    public static int fiboHelper(int n, int[] arr){

        if(n <= 0) {
            return arr[0];
        }

        else if(n == 1) {
            return arr[1];
        }

        else {

            if( arr[n-1] != 0 && (arr[n-2] != 0 || (arr[n-2] == 0 && n-2 == 0))){    
                return arr[n] = arr[n-1] + arr[n-2]; 
            }

            else if (arr[n-1] == 0 && arr[n-2] != 0 ){
                return arr[n] = fiboHelper(n-1, arr) + arr[n-2]; 
            }

            else {
                return  arr[n] = fiboHelper(n-2, arr) + fiboHelper(n-1, arr );
            } 

        }             
    }