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

Question

Мне трудно понять, почему

#include <iostream>

using namespace std;

int fib(int x) {
    if (x == 1) {
        return 1;
    } else {
        return fib(x-1)+fib(x-2);
    }
}

int main() {
    cout << fib(5) << endl;
}

приводит к ошибке сегментации. Как только x падает до 1, разве он не должен возвращаться?

Answer 1

Когда x==2 вы звоните fib(1) и fib(0):

return fib(2-1)+fib(2-2);

Подумайте, что произойдет, когда fib(0) будет оценено ...

Answer 2

Причина в том, что последовательность Фибоначчи начинается с двух известных объектов, 0 и 1. Ваш код проверяет только один из них (будучи одним).

Измените свой код на

int fib(int x) {
    if (x == 0)
        return 0;

    if (x == 1)
        return 1;

    return fib(x-1)+fib(x-2);
}

Чтобы включить 0 и 1.

Answer 3

Почему бы не использовать итерационный алгоритм?

int fib(int n)
{
    int a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }           
    return b;
}

Answer 4

По определению, первые два числа в последовательности Фибоначчи - это 1 и 1 или 0 и 1. Поэтому вы должны обработать это.

#include <iostream>
using namespace std;

int Fibonacci(int);

int main(void) {
    int number;

    cout << "Please enter a positive integer: ";
    cin >> number;
    if (number < 0)
        cout << "That is not a positive integer.\n";
    else
        cout << number << " Fibonacci is: " << Fibonacci(number) << endl;
}

int Fibonacci(int x) 
{
    if (x < 2){
     return x;
    }     
    return (Fibonacci (x - 1) + Fibonacci (x - 2));
}

Answer 5

Это моё решение проблемы Фибоначчи с рекурсией.

#include <iostream>
using namespace std;

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

int main() {
    cout << fibonacci(8);
    return 0;
}

Answer 6

Я думаю, что это решение короткое и выглядит красиво:

long long fib(int n){
  return n<=2?1:fib(n-1)+fib(n-2);
}

Редактировать: как упоминал jweyrich, истинная рекурсивная функция должна быть:

long long fib(int n){
      return n<2?n:fib(n-1)+fib(n-2);
    }

(потому что fib (0) = 0. но исходя из приведенной выше рекурсивной формулы, fib (0) будет 1)

Чтобы понять алгоритм рекурсии, вы должны нарисовать на бумаге, и самое главное: «Думай нормально, как часто».

Answer 7

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

в последовательности Фибоначчи первые 2 числа всегда равны 1, затем каждый раз, когда значение становится 1 или 2, оно должно возвращать 1

Answer 8

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

Однако использование рекурсии для получения числа Фибоначчи является плохой практикой, потому что функция вызывается примерно в 8,5 раз больше, чем полученное число. Например. чтобы получить число Фибоначчи от 30 (1346269) - функция вызывается 7049122 раза!

Answer 9

int fib(int x) 
{
    if (x < 2)
      return x;
    else 
      return (fib(x - 1) + fib(x - 2));
}

Answer 10

int fib(int x) 
{
    if (x == 0)
      return 0;
    else if (x == 1 || x == 2) 
      return 1;
    else 
      return (fib(x - 1) + fib(x - 2));
}