Рекурсивный Фибоначчи .. не знаю, что происходит

Question

Недавно я создал код для процедурной функции в приложении на языке c ++ для вычисления F (n) в последовательности Фибоначчи.

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

Это функция, которую я использую ... и код, полученный из сети. У меня проблема с кодом из сети, и мой код точно такой же (почти), но ОБА дают неправильное значение ...

http://codepad.org/pMKs4kvb

Что происходит?

Answer 1

Ну, проще говоря, ваша функция распечатывает следующие серии:

1, 1, 2, 3, 5, 8 ...

И, следовательно, F(5) = 8 (если мы говорим, что здесь индексирован ноль).Если вы хотите, чтобы было напечатано следующее:

0, 1, 1, 2, 3, 5, 8 ... 

Какая последовательность распознается OEIS, тогда все, что вам нужно сделать, это убедиться, что вы определили F(0) = 0.В этой степени ваша функция должна быть просто:

int FibiRec(int n) {
    if (n == 0 || n == 1) {
        return n; // IMPORTANT
    } else {
        return FibiRec(n-1) + FibiRec(n-2);
    }
}

В то же время я хотел бы добавить: ваша функция имеет ужасную сложность по времени O(2^n).С вашей функцией попробуйте сгенерировать 40-е или 100-е число Фибоначчи, и вы поймете, о чем я говорю.

Answer 2

Полагаю, вам нужно добавить еще одно условие n==2 в цикл if ... ваша программа должна быть ...

int FibiRec(int n){
        int result = 0;
        if (n == 0 || n == 1 || n==2){
            return 1;
        }else{
            return FibiRec(n-1) + FibiRec(n-2);
        }
    }

Это потому, что при n = 2 будут вызваны FibiRec (1) и FibiRec (0), которые являются вашими условиями остановки ....

Answer 3

Ваша нумерация начинается с 0 ..., а процедурная нумерация начинается с 1

n: 0, 1, 2, 3, 4, 5

F (n): 1, 1, 2, 3, 5, 8