Рекурсивные функции с использованием рядов Фибоначчи

Question

Я самообучающийся C++ от Sams Teach Yourself C++ В один час дня и на странице 150 автор обсуждает рекурсивные функции с использованием серии Фибоначчи.

Он использует следующий код:

#include <iostream> 
using namespace std; 

int GetFibNumber(int FibIndex) 
{ 
    if(FibIndex < 2) 
     return FibIndex; 
    else 
     return GetFibNumber(FibIndex - 1) + GetFibNumber(FibIndex - 2); 
} 

int main() 
{ 
    cout << " Enter 0 based index of desired Fibonacci Number: "; 
    int Index = 0; 
    cin >> Index; 

    cout << " Fibonacci number is: " << GetFibNumber(Index) << endl; 

    return 0; 

} 

В чем разница между наличием

возврата GetFibNumber (FibIndex - 1) + GetFibNumber (FibIndex - 2);

и

возвращение FibIndex - 1 + FibIndex - 2;

Почему вы должны вызвать функцию внутри себя?

Заранее спасибо!

Answer 1

Вы спрашиваете: «Почему вы должны вызвать функцию внутри себя?» Ну, строго, вы этого не делаете.

Fibonacci sequence представляет собой последовательность чисел, определенных настоящим математической рекурсии:

• = 0
• = 1
• _п = а _n-1 + a _n-2

Исходная функция вычисляет эту последовательность, хотя и неэффективно. Если Index равно 0, он возвращает 0; если он равен 1, он возвращает 1. В противном случае он возвращает GetFibNumber(Index - 1) + GetFibNumber(Index - 2), что и является математическим определением. Для каждого элемента последовательности вы должны добавить два предыдущих слова в последовательности.

Ваш код просто возвращает Index - 1 + Index - 2, что даст другую численную последовательность. Для сравнения:

• Фибоначчи: 0, 1, 1, 2, 3, 5, 8, 13, 21, 36 ...
• Ваш: 0, 1, 1, 3, 5, 7, 9 , 11, 13, 17 ...

Но в остальном вам не нужна рекурсивная функция для вычисления этой математической рекурсии. Все, что вам нужно, это просто for петля:

int GetFibNumber(int FibIndex) 
{ 

    if(FibIndex < 2) 
     return FibIndex; 

    int a_n_2 = 0, a_n_1 = 1, a_n; 

    for (i = 2; i < FibIndex; i++) 
    { 
     a_n = a_n_1 + a_n_2; 
     a_n_2 = a_n_1; 
     a_n_1 = a_n; 
    } 

    return a_n; 
} 

Такой подход будет гораздо быстрее, а также.

Рекурсивный метод математически корректен. Тем не менее, он медленнее, потому что он не использует повторные вычисления. Он вычисляет _n-1, перерабатывая рекурсию на обратном пути до . Затем он вычисляет _n-2 без повторного использования какой-либо работы, которая сгенерировала _n-1. И если вы считаете, что это отсутствие повторного использования происходит на каждом этапе рекурсии, вы увидите, что running time grows exponentially for the recursive function. Он растет линейно для цикла for.

---

_{Advanced тема: Существует способ сделать рекурсивную версии работать быстрее, и это может быть важно знать, если вы столкнулись с проблемой программирования, который наиболее легко определен рекурсивно. Как только вам станет намного удобнее C++, найдите memoization. Воспоминаемый рекурсивный Фибоначчи дает линейное наихудшее время выполнения и постоянное время выполнения для повторных поисков (при условии, что поиск memo сам является O (1)).}

Answer 2

Использование версии, не использующей рекурсию, неверно. Он будет правильно вычислять только первые числа Fiboonacci. Попробуйте вычислить первые 10 чисел Фибоначчи, используя две версии, и вы увидите, что две версии вычисляют две разные последовательности.

Answer 3

Функция GetFibNumber вычисляет N-е число в серии Фибоначчи. Если вы просто взглянете на объяснение на http://en.wikipedia.org/wiki/Fibonacci_number, это будет рассчитано путем добавления чисел Nth-1 и Nth-2 в серии Fibinacci. И это именно то, что делает функция. Вы предоставляете функцию с индексом в серии Fibonacci, который вы хотите вычислить (скажем, 6, это должно иметь 8 результат).

Для расчета 6-го элемента в серии Фибоначчи необходимо добавить 5-й и 4-й элементы вместе. Поэтому вам сначала нужно их вычислить. Здесь вы можете выполнить рекурсию. Вы можете позволить функции вызвать себя; но вместо того, чтобы называть его снова значением 6 в качестве параметра, вы теперь используете 5 и 4. Это снова приведет к той же проблеме (вам нужно вычислить пятый элемент, добавив элементы 4 и 3) и т. д. и т. д.

С помощью рекурсивной функции вы можете просто повторно использовать код для повторения одного и того же вычисления снова и снова, пока не достигнете определенной точки, где у вас есть ответ для вычисления (в этом случае, если N = 1 или N = 0, эти случаи приведет к 1).

Answer 4

Я бы предложил, так как вы все еще учитесь, программировать это как рекурсивно (как это сделал автор), так и использовать цикл (while, for). Это, скорее всего, покажет вам ответ на то, как этот алгоритм будет создан.

Подсказка 1: Вы должны знать, что Fibonnaci последовательности построены на двух начальных значений ...

Подсказка 2: Потому что, когда речь идет о рекурсии, вы должны знать, каким образом результаты функции сохраняются. Это также объяснит ваш вопрос.

Answer 5

Они не являются равнозначными и, конечно же, не будут вычислять фибонановую последовательность.Рекурсия можно рассматривать как дерево, так, чтобы вычислить Fib (8) говорят, по определению, мы принимаем Фибо (7) + Фибо (6)

 Fib(8) 
     / \ 
    Fib(7) Fib(6) 

Что в свою очередь требует вычисления Fib (6), Fib (5), Fib (4) следующим образом:

    Fib(8) 
      /  \ 
      Fib(7)  Fib(6) 
     /  \ / \ 
    Fib(5) Fib(6) Fib(5) Fib(4) 

И так далее. То, что вы делаете, будет производить другой, глубина 1 дерево:

Fib(8) 
    / \ 
    7  6 

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