slt a tous,

dans le bouquin avec lequelle j´apprend le c++, il m´explique ce qu´est la récursivité et me donne un exemple d´algorithme récursif:

1. include < iostream>

using namespace std;

double factorielle ( int n)
{
if ( n>1) return n*factorielle(n-1);
else return 1;
}

int main ( )
{
int a=0;
cout<<"saisissez un nombre:"<<endl;
cin>>a;
cout<<factorielle(a)<<endl;
return 0;
}

le probleme est que je ne comprend pas du tout ce qu´est la récursivité avec ce programme. autant sur lepapier le principe semble simple, autant dans un programme je ne vois pas du tout. si quelqu´un pouvait m´aider ce serait tres sympa

merci d´avabnce

La récursivité c´est le fait qu´une fontion s´appelle d´elle même, je crois, comme le montre ton exemple.

c´est justement ca que je ne comprend pas bien, qu´esy ce que tu veux dire par " elle s´appelle elle meme"?

bah , dans la fonction , bah on appelle la fonction ^^

merci sonic

ta compris?

chuis trop fort !

nn deso de te decevoir mais c´était de....
l´ironie

double factorielle ( int n)
{
if ( n>1) return n*factorielle(n-1);
else return 1;
}

dans la fonction factoriel , on appelle la fonction factorielle

la fonction ´appelle donc elle meme ( jusqua que nsoit plus petit que 1)

c´est donc RECURSIF!

En gros, la factorielle de N c´est :

factorielle(N) = 1*2*3*...*(N-1)*N
Le produit de tous les entiers naturels de 1 à N.

On peut commuter tous les termes :

factorielle(N) = N*(N-1)*...*3*2*1
Dans ce sens, on voit qu´on multiplie à chaque fois en enlevant 1, jusqu´à ce qu´on arrive à 1 !

Si tu découpes un peu ça te donne :
factorielle(N) = N * [(N-1)*...*3*2*1]
La partie à droite peut être assimilable à factorielle(N-1) si tu regardes bien ( On multiplie bien les facteur de 1 à ( N-1) dans l´expression entre crochets)

La récursivité c´est donc de faire une fonction qui va s´appeler elle même en modifiant son argument jusqu´à un certain temps

Ici, la fonction va trouver la valeur 1 en " fin de récursivité", puis elle va retournercette valeur, la multiplier par 2, retourner, la multiplier par 3, retourner, la multiplier par 4 !

Un exemple simple de récursivité m´a été présenté par JYY :
Imagine un bitmap. C´est assimilable à un tableau de pixels. Comment coderais-tu la fonction remplissage, qui colore en COULEUR tous les points adjacents au point cliqué, ayant la même couleur que le point cliqué ? ( Ce que je décris, c´est le pot de peinture de Paint ; ))

Hé bien on le fais en récursif :

Colorer_pixel_et_proches(Couleur ANCIENNE_COULEUR, Couleur NOUVELLE_COULEUR, int x, int y)
{
if(Couleur_Image[x][y] == ANCIENNE_COULEUR)
{
Couleur_Image[x][y] = NOUVELLE_COULEUR;

Colorer_pixel_et_proches(ANCIENNE_COULEUR, NOUVELLE_COULEUR, x-1, y);
Colorer_pixel_et_proches(ANCIENNE_COULEUR, NOUVELLE_COULEUR, x+1, y);
Colorer_pixel_et_proches(ANCIENNE_COULEUR, NOUVELLE_COULEUR, x, y-1);
Colorer_pixel_et_proches(ANCIENNE_COULEUR, NOUVELLE_COULEUR, x, y+1);
}
}

Lorsqu´on clique avec le pinceau sur un pixel, on récupère le ( x;y) de la souris, la couleur du pixel [x][y] qui est l´ANCIENNE_COULEUR, la couleur du pinceau qui est la NOUVELLE_COULEUR.
On lance cette fonction :
Si le pixel en question est de l´ANCIENNE_COULEUR, on change sa couleur, et on lance la fonction sur les 4 pixels autour de lui !
Si un des pixels autour de lui n´est pas de l´ANCIENNE_COULEUR, alors la fonction récursive est arrêtée. Tant que le pixel à côté est de l´ANCIENNE_COULEUR, on change sa couleur, et on analyse les 4 pixels autour de lui

Si tu comprends pas c´est pas très grave, mais ça devrait être plus simple que la factorielle, qui utilise la récursivité en return...Là on ne se sert de la récursivité que pour analyser les points autour du point qu´on est en train d´analyser

PS : Il faut penser à vérifier que NOUVELLE_COULEUR est différente d´ANCIENNE_COULEUR dans mon exemple, sinon ça va faire un Stack Overflow je pense

Correction :

Ici, la fonction va trouver la valeur 1 en " fin de récursivité", puis elle va retournercette valeur, la multiplier par 2, retourner, la multiplier par 3, retourner, la multiplier par 4, ( ...), retourner, la multiplier par n, et finalement la fonction retourne ce résultat final qui est la factorielle de n !

Merci pour les précisons Ptival et pour ce magnifique exemple

J´esprèe que je lai pas plus embrouillé qu´il ne l´était avec mon message à rallonge, mais fallait bien ce gros paquet de texte pour être précis

Je profite de ce topic sur ce sujet passionant pour faire part aux forumeurs des avantages inconvénients de la récursivité/itérativité, car la majeure partie des livres de progs grand public s´arrêtent au simple constat : " l´itérativité c´est mieux. point."

( Ceci dit les thèmes abordés sont un peu complexes, inutile de s´attarder dessus pour l´instant si ca vous gonfle)

Mais alors c´est qui le mieux ?
La récursivité ou l´itérativité ?
Ca dépends...

La récursivité s´effectue sur un ensemble d´éléments gradués, càd qu´à chaque élément ( un nombre entier, un objet, un pingouin, etc...), on associe un entier appelé graduation. Cette graduation est représentative de la complexité de l´élément : les éléments simples possèdent une graduation faible, alors que les éléments plus complexes possèdent une valeur de graduation plus élevée ( dans le cas de la factorielle, l´ensemble considéré est celui des nombres entier, et la graduation est simplement égale à la valeur de ces dits nombres).

On dispose en outre d´une fonction dite de descente, mettant en relation ces élément entre eux, dans le sens d´une simplification ( passer d´éléments donner à d´autres un peu plus simples, etc...).

Par exemple la fonction de descente usuelle : n -> n-1 est celle utilisée dans la fonction factorielle : l´appel récursif implique l´élément de complexité n-1.

Il existe d´autres types de fonctions de descente, nottament celle du " diviser pour régner" : n -> n/2, mais les choses se complexifient.

A partir de ca : si on connait l´ensemble d´éléments, la graduation et la fonction de descente, on peut savoir s´il vaut mieux procéder récursivement ou itérativement :

Si la fonction récursive est terminale ( càd qu´elle se termine par le retour direct d´une valeur à la fonction du programme appelante, sans avoir besoin de retourner de résultat intermédiaire), alors il s´agit de la meilleure version en terme de rapidité et on a pas intérêt à dérecursifier.

Exemples :

- Récursivité non terminale :

int facto(int x )
{
   if(x==0 || x==1 )
      return 1;
   else
      return x*facto(x-1);
}

- Récursivité terminale :

/ / Fonction utilitaire non appelée explicitement
int facto_util(int resultat_partiel, int x )
{
   if(x==0 || x==1 )
      return resultat_partiel;
   else
      facto_util(x*resultat_partiel,x-1);
}

inline int facto(int x )
{
   return facto_util(0, x )
}

On remarque que dans la version terminale, le résultat est renvoyé directement par la fonction, tandis que dans la version non terminale, le résultat final doit d´abord être calculé en faisant le produit au sein des fonctions facto appelantes, ce qui perd du temps.

Cependant, on ne peut pas toujours obtenir une récursion terminale...

Si la fonction récursive est non terminale :

- Soit elle est associée à la fonction de descente usuelle, n -> n-1, dans ce cas on a intérêt à dérecursifier...

- Soit elle n´est pas associée à la fonction de descente usuelle, dans ce cas on pourrait dérecursifier, mais ca ne présenta pas d´intérêt.

( corrige moi dnob si je dis une erreur ( j´ai pas mon cour sous les yeux ) )

extasy -> Au fait, ta fonction factorielle, types-la en int, le double ne sert à rien là

lag-it -> Il faudrait pas vérifier le cas où le mec tente de faire une facto d´un entier négatif ? :\

C´est tout à fait ça, il n´y a pas d´erreur ( sauf peut-être une imprécision sur la récursivité terminale, puice que là tout ce que tu nous donne est une récursivité simple, mais ça n´a pas d´importance).

Donc ça vaut bien 11/20 . ..
Bah ouais, les notes audessus, je pense qu´elles servent à rien.

Nous nous retrouvons la semaine prochaines pour une colle sur le paradigme diviser pour regner.

C´est une fonction pour programmeurs intelligents
( nan c´était juste pour l´exemple, mais effectivement )

Lol dnob
Par contre c´est quoi l´histoire de la récursivité simple ? La fonction factorielle et une récursive simple à la base, non ?

oui, oui.

Mais en pratique quand tu as une récursivité simple de ce type ( c´est à dire que la fonction ne s´appelle qu´une fois, et que le nombre d´itaration est fonction simple du paramètre) tout les fonctions récursive sont terminale, ou peuvent être ramener à une fonction récursive terminale.

C´est juste que tu n´a pas préciser qu´il pouvait y avoir des cas plus compliqué ( sinon t´aurais eu 11.5).

Héhé

Que EBP vous maudisse tous !

L´utilisation de la récursivité ( en mon humble avis) ne fait que gaspiller une montagne de resources.

Voyont le code suivant :

int loop(int value)
{

int result = 1;

for ( ; value > 1 ; value-- )
{
result = result*value;
}

return result;

}

int facto(int x )
{
if(x==0 || x==1 )
return 1;
else
return x*facto(x-1);
}

int main ( int argc , char *argv[])
{

printf("loop: %d\n" , loop(5) ) ;
printf("facto: %d\n" , facto(5) ) ;
getchar();

return 0;
}

Ça donne le même résultat, mais la récursive sera beaucoup plus lente je crois. Pourquoi ? Car avec des fonctions récursives ont, permetter moi le québécisme, " gosse" dans la stack ( pile) à n´en plus finir ! ( Imaginez si on doit récursiver une centaine de fois, la pile va gonfler et puis exploser . ..).

Pire encore : en C++ si nous nous trouvons dans une classe ( nous sommes Da méthode), en plus on va pusher/poper this ! Inutile ! Inutile !

Dans notre cas la version itérative ( loop()) est beaucoup plus rapide.

Bien entendu ce n´est que mon humble avis, j´suis pas un pro, je peux faire des erreurs . ..

Kali