Suite de Fibonacci

**Évariste Galois** · 19/07/2005, 22h01

Bonjour,

J'ai créer une petite fonction destinée à calculer le n-ième terme de la suite de Fibonacci : 1,1,2,3,5,8,13 ... (chaque terme égale la somme des deux précédents)

Pourriez-vous y jeter un coup d'oeil (tout marche, tout fonctionne mais j'aimerais avoir votre avis ...) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
/* Suite de Fibonacci, chaque terme est égale à la somme de deux précdents : 1,1,2,3,5,8 ...
Le n ième terme est donc la somme des termes (n-1) et (n-2) si n>2 (n entier positif) */
long int fib(unsigned int n)
{
     long int resultat=1;                    // Le n ième terme
     long int terme_1 = 1, terme_2 = 1;      // Les termes n-1 et n-2
 
     if (n < 3) return 1;
 
     resultat = 2;
     for (int C=3; C<=n; C++)
     {
         // n = (n -1) + (n - 2)
         resultat = terme_1 + terme_2;
         /* Logiquement, lorsqu'on passe au terme suivant, le terme (n-1)devient le terme (n - 2) et le terme (n - 2) devient le terme n */
         terme_1 = terme_2;
         terme_2 = resultat;
     }
     return resultat;
}

Est ce qu'il y certaines choses que j'ai faites de travers (niveau de l'algo) ? Y a il des améliorations a apportées ?

merci

**capitN.flam** · 19/07/2005, 22h53

la première chose que tu peux changer c'est le type de retour etant donné que ce sera toujours un nombre >0 tu peux retourner un unsigned long de plus tu prends en paramètre un unsigned donc...

en ce qui concerne la méthode en elle même étant donné que je n'ai codé fibonacci qu'en récursif je ne peux pas te dire si elle est bonne ou pas mais comme tu dis que cela fonctionne c'est que cela doit être vrai.

**bigboomshakala** · 19/07/2005, 23h54

bonjour,

la suite de Fibonacci commence à 0

conditions initiales :
F(0)=0
F(1)=1

suite:
F(n)=F(n-1)+F(n-2)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
type1 Fib(type2 n)
{
   type1 F" = 0;
   type1 F' = 1;
   type1 F = F";
 
   for (int i = 0; i <= n; i++)
   {
      F = F" + F';
      F" = F';
      F' = F;
   }
   return F;
}

**Évariste Galois** · 20/07/2005, 14h19

Envoyé par capitN.flam

la première chose que tu peux changer c'est le type de retour etant donné que ce sera toujours un nombre >0 tu peux retourner un unsigned long de plus tu prends en paramètre un unsigned donc...

Bonne idée, je vais changer ça

Envoyé par bigboomshakala

la suite de Fibonacci commence à 0

Ah, dans mon livre C++ il prétendent que cela commence à 1 ...

Sinon ils proposent (dans le livre) une méthode en récursif :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
int fib(int n)
{
    if (n < 3) 
       return 1;
    else 
       return (fib(n-2) + fib(n-1));
}

Mais il parait qu'elle n'est pas très efficace (ils ne précisent pas pourquoi). Ma fonction est elle plus efficace que celle-ci ? Si oui pourquoi ?

merci

**Évariste Galois** · 20/07/2005, 14h27

Oh oui. Ma fonction est bien plus rapide que celle utilisant la récursivité, mais je ne compend pas pourquoi ...

Faut-il en conclure que la récursivité est une méthode à proscrire lorsque c'est possible ?

merci

**Tarrke** · 20/07/2005, 15h02

De mémoire :

lorsque tu fait une fonction récursive tu l'appel un nombre important de fois, à ce moment là le temps d'appel de la fonction entre en compte devant le temps de calcul.
Si tu appel 100 fois la même fonction avec 0.01 sec de temps d'appel et 0.1 sec de temps de calcul tu mettra 11 sec au lieu des 10 sec de temps de calcul.
La récursivité est bien mais pas top niveau performances.

tu peux faire le même essait avec le calcul de factoriel :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
unsigned long fact( int n )
{
  if( n <= 2 ) return n;
  return n*fact( n-1 );
}

ou alors la version plus rapide :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
unsigned long fact( int n )
{
  unsigned long res = 1;
  for( int i = n; i > 1; --i )
  {
     res *= i;
  }
  return res;
}

et là tu devrait voir la différence...

Tarrke

**Évariste Galois** · 20/07/2005, 20h11

Ah bon, eh bien oui en fait c'est logique.
Chaque appel de fonction ralentit le programme. Et la récursivité ce n'est pas évident à maîtriser ...

Bon, conclusion -> vive les boucles for

merci

**Tarrke** · 21/07/2005, 08h53

De rien,

mais n'oublie pas, la programmation en réccursif est plus facil pour certains, en effet beaucoup de mathématiciens préfèrent un algo récursif car il le comprennent, mais à nous de le dérécursifier si possible.
Il ne faut pas bannir le récursif pour ses performances, une heure de codage et une heure d'execution valent peut-être meiux que dix heures de codage et 30 minutes d'execution non ?

Ravis d'avoir pu aider
Tarrke

**JolyLoic** · 21/07/2005, 10h30

+1, surtout si on rajoute 5 minutes de maintenance d'un côté, et 5 jours de l'autre

Pour info, il existe des cas de récursivité qu'un compilateur est à même d'optimiser plus aisément (cherche récursivité terminale pour plus d'info), mais on commence généralement à perdre en clarté et simplicité du code.

Enfin, en terme de performances, notons qu'il est possible si l'on souhaite calculer la valeur d'un membre dont le rang est connu au moment de la compilation de calculer cette valeur à la compilation elle aussi. Et là, comme pour tout calcul à la compilation, la récursivité est la seule méthode disponible.

**Évariste Galois** · 21/07/2005, 13h36

Envoyé par JolyLoic

comme pour tout calcul à la compilation, la récursivité est la seule méthode disponible

Ah, ça je ne savais pas tient.
De toute façon je ne jette pas la récursivité, je suppose que ça me servira bien un jour ...

merci

**narkhor** · 21/07/2005, 14h42

et puis faire de la récursivité n'empèvhe pas de réfléchir!
essayez ce programme, deux fonction qui calcule le nième terme de suite de fibonaci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
 
int string2int(char* s, int p = 0){
  if( *s != '\0' )
    return string2int(s+1, 10*p + *s -'0');
  else return p;
}
 
unsigned long fibonaci_recur(unsigned int n){
  if(n<2)return 1;
  else return fibonaci_recur(n-1) + fibonaci_recur(n-2);
}
 
unsigned long fibonaci_updated(unsigned int n){
  if(n<2)return 1;
  else {  // n>=2
    int fm2 = fibonaci_updated(n-2), fm3 = 0;
    if(n>2) fm3 = fibonaci_updated(n-3);
    return 2*fm2 + fm3;
  }
}
 
using namespace std;
 
int main(int argc, char* argv[]){
  if(argc<2)cerr << "Il faut un argument !" << endl;
  int n = string2int(argv[1]);
 
  cout << "lancement fonction 1..." << endl;
  cout << "le résultat est : " << fibonaci_recur(n) << endl << endl;
 
  cout << "lancement fonction 2..." << endl;
  cout << "le résultat est : " << fibonaci_updated(n) << endl << endl;
}

je ne sais pas comment chronométré alors je ne l'ai pas fait. si quelqu'un veux le faire

ne pas oublier aussi que le C++ n'est pas spécialement optimiser pour la récursivité, un language tel que le CAML est beaucoup plus efficace dans ce domaine.

**bruno_pages** · 21/07/2005, 19h22

oui C++ n'est pas le meilleur pour gerer les recursions, mais de toute facon une vraie gestion ne peut se faire qu'avec un interpreteur, et des langages que je connais la palme revient à Lisp de ce cote : Vlisp & LeLisp (et mon lisp et logo persos sur Goupil il y a pret de 20 ans !) traitait par exemple les recursions "enveloppé" du type de celle de factorielle en recursif : (* n (fact (- n 1))) qui n'empilait rien car la multiplication etait faite tout de suite et non au retour. Ceci est théoriquement possible à faire avec un langage compile même si ce n'est pas le cas, par contre les cas de recursions croisées (A appelle B qui appelle A etc ..., ou avec plus de fonctions intermediaires) sont plus dure à traiter à la compilation.

A part cela la récursion permet de faire des codes concis et clairs, ce ne sont pas les tours de hanoi qui vont me contredire