Récursive De Fibonacci

j'ai du mal à comprendre pourquoi

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

résulte en un défaut de segmentation. Une fois que x est descendu à 1 ne devrait-il pas éventuellement revenir?

34
demandé sur Jonathan Leffler 2009-10-05 11:51:12

13 réponses

Quand x==2 vous appelez fib(1) et fib(0):

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

réfléchir à ce qui va se passer quand fib(0) est évaluée...

146
répondu Georg Fritzsche 2009-10-05 08:07:34

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.

38
répondu LiraNuna 2009-10-05 07:56:34

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;
}
11
répondu Dzmitry Huba 2009-10-05 08:28:22

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));
}
7
répondu Vanji 2014-08-12 18:03:40

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".

3
répondu hqt 2013-10-28 18:32:10

#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;
}
3
répondu Pedro Eugénio 2016-03-15 13:13:24
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

2
répondu noelyahan 2013-03-03 15:00:34
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));
}
1
répondu user2331083 2013-04-29 07:10:00
int fib(int x) 
{
    if (x < 2)
      return x;
    else 
      return (fib(x - 1) + fib(x - 2));
}
1
répondu zod 2013-09-17 12:38:41
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!

1
répondu Jokerius 2013-12-10 09:19:24

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

0
répondu Cadence Weddle 2016-11-02 21:18:04

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;
}
0
répondu Md. Ashraful Haque 2017-02-02 15:51:54

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.

0
répondu Артем Васильев 2018-08-05 12:39:05