Récursive De Fibonacci

La raison en est que la séquence de Fibonacci commence par deux entités connues, 0 et 1. Votre code ne vérifie que l'un d'eux (étant un).

changez votre code en

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

    if (x == 1)
        return 1;

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

pour inclure 0 et 1.

Pourquoi ne pas utiliser l'algorithme itératif?

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;
}

par définition, les deux premiers nombres dans la séquence de Fibonacci sont 1 et 1, ou 0 et 1. Par conséquent, vous devez manipuler.

#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));
}

je pense que cette solution est courte et semble agréable:

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

Edit : comme jweyrich mentionné, la vraie fonction récursive doit être:

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

(parce que fib (0) = 0. mais sur la base de la formule récursive ci-dessus, fib (0) sera 1)

pour comprendre l'algorithme de récursion, vous devriez dessiner sur votre papier, et la chose la plus importante est : "Pensez normal aussi souvent".

#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;
}

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

dans la séquence de fibonacci d'abord 2 nombres se suivent toujours à 1 puis chaque fois que la valeur est devenue 1 ou 2 il doit retourner 1

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));
}

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

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

cependant, utiliser la récursion pour obtenir le nombre de fibonacci est une mauvaise pratique, parce que la fonction est appelée environ 8,5 fois que le nombre reçu. Par exemple: pour obtenir le nombre de fibonacci de 30 (1346269) - la fonction est appelée 7049122 fois!

ma solution est:

#include <iostream>


    int fib(int number);

    void call_fib(void);

    int main()
    {
    call_fib();
    return 0;
    }

    void call_fib(void)
    {
      int input;
      std::cout<<"enter a number\t";
      std::cin>> input;
      if (input <0)
      {
        input=0;
        std::cout<<"that is not a valid input\n"   ;
        call_fib();
     }
     else 
     {
         std::cout<<"the "<<input <<"th fibonacci number is "<<fib(input);
     }

    }





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

    else if (x>0)
   {
        return fib(x-1)+fib(x-2);
    }
    else 
     return -1;
    }

il retourne fib (0)=0 et error if negitive

je pense que c'est la meilleure solution de fibonacci en utilisant la récursivité.

#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
ull FIBO[100005];
using namespace std;
ull fibo(ull n)
{
    if(n==1||n==0)
        return n;
    if(FIBO[n]!=0)
        return FIBO[n];
    FIBO[n] = (fibo(n-1)+fibo(n-2));
    return FIBO[n];
}
int main()
{
    for(long long  i =34;i<=60;i++)
        cout<<fibo(i)<<" " ;
    return 0;
}

je pense que toutes ces solutions sont inefficaces. Ils exigent beaucoup d'appels récursifs pour obtenir le résultat.

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

ce code nécessite 14 appels pour obtenir le résultat pour fib(5), 177 pour fin(10) et 2.7 kk pour fib (30).

vous devriez mieux utiliser approche ou si vous souhaitez utiliser la récursivité essayez ceci:

unsigned fib(unsigned n, unsigned prev1 = 0, unsigned prev2 = 1, int depth = 2)     
{
    if(n == 0) return 0;
    if(n == 1) return 1;
    if(depth < n) return fib(n, prev2, prev1+prev2, depth+1);
    return prev1+prev2;
}

cette fonction nécessite n appels récursifs pour calculer le nombre de Fibonacci pour N. Vous pouvez toujours l'utiliser en appelant fib (10) parce que tous les autres paramètres ont des valeurs par défaut.