[récursivité] Fermé

Question

bonjour tout le monde
je suis étudiante , je veux écrire un programme en lagage c qui effectue des traitements sur les arbres binaires, mais j'ai eu beaucoup de difficuletés a programmer un truc pareil car les algorithmes utilisées dans le traitement de ce genre de problémes reposent sur le principe de récursivité. et bien mon probléme c la récursivité, j'arrive pas à la comprendre en plus je trouve pas assez d'inforamtions sur ça . donc svp si quelqu'un posséde des informations ,où sait où je peux trouver des solutions à mon probleme qu(il n'ésite pas a me contacter.
Merci.

mamiemando · Answer

La récursivité ressemble au raisonnement par récurrence que tu as du voir en math. Sauf que dans le raisonnement par récurrence on va de n à n+1 en partant d'un rang (par exemple 0). La récursivité c'est là même chose mais dans l'autre sens. Le rang 0, où l'on s'arrête correspond à ce qu'on appelle le cas d'arrêt.

Exemple : factorielle 5! = 1*2*3*4*5

// méthode itérative :
unsigned int fact(unsigned int x){
  unsigned int i,res = 1;
  for(i=1;i<x;++i){
    res *= i; // ou si tu préfères res= res * i;
  }
}

// methode recursive : cas d'arrêt 0 ou 1:
unsigned int fact_rec(unsigned int x,unsigned int res){
  if ( x == 0 || x == 1 ) return 1;
  return fact_rec(x-1,res*x);
}

unsigned int fact2(unsigned int x){
  return fact_rec(x,1);
}

Tu constates que pour la version récursive il faut transmettre dans l'appel recursif la valeur de res (fonction fact_rec). Comme l'utilisateur ne doit pas avoir à l'initialiser à 1, on écrit une fonction fact2 qui est celle qu'il manipulera sans avoir à se soucier de la valeur à mettre pour res.

J'espère que pour toi c'est plus clair ! Dans le cas d'un arbre on est effectivement de faire des appels récursifs donc il faut réfléchir à tes cas d'arrêts (on a atteint une feulle par exemple) et parcourir chaque branche fille dans ton appel récursif.

Bonne chance

Darshu · Answer

Hum, la récursivité n'est pas forcément facile à comprendre au début, mais dès que t'a eu le déclic tout marche bien.

Le principe c'est que la fonction s'appelle elle même, ce qui risque de générer des appels infinis ! Il faut donc bien aire attention à mettre des conditions d'arrêt, et à faire évoluer les variables pour qu'elles se mettent bien à jour.

Après te parler de la récursivité en général comme ça, c'est pas facile ... Pour les arbres binaires, ça peut servir à faire une recherche sans savoir combien d'enregistrement il y a, jusqu'à trouver le bon si on a un pointeur dessus par exemple ...

Voila un exemple de fonction récursive toute bête qui calcule la somme des n premiers entiers :

int somme(int n)
{
int s=0;
if (n > 1)
return s += somme(n-1);
else
return 1;
}

En espérant que ça peut t'aider à comprendre ce que c'est ...

mamiemando · Answer

Alors en fait tu es dans un cas très proche du fact2 que je t'ai proposé. En fait tu as deux variables, le noeud courant (qui correspondant à mon x), et le total calculé (ma variable res). Tu vois donc immédiatemment qu'il va falloir faire un truc dans le même genre. Ta fonction recursive (qui correspond a mon fact_rec) calculera la taille d'un sous-arbre à un noeud donné et prendra en paramètre le total calculé. La fonction faisant le calcul sera donc juste un appel à cette fonction avec res=0 et comme noeud la racine.

Comme c'est vraiment très proche et que tu n'es pas loin de la solution je te laisse chercher mais tu y es presque. Bien sûr si tu ne t'en sors pas je t'aiderai.

Ne perds pas de vue que dans ton cas la recursivité se fait sur deux "fils" le fils gauche et le fils droit mais que sinon le raisonnement est similaire.

Bonne chance

lilia2006 · Answer

bonjour
merci de vous interesser a mon probleme, et bien g pensé a voir sur google, mais ça m'a pas beaucoup aidé, pour comprendre g essayé de faire le déroulement de ces fonctions récursives sur un papier en utilisant les piles , mais je m'embrouille tout le temps, je ne sais pas pourquoi je suis la seule a trouver ça si compliqué, en plus ne soyez pas surpris, je ne comprend toujours pas l'histoire de ce nb initialisé a zéro.
merci

mamiemando · Answer

Je n'ai pas testé mais c'est quelque chose dans l'idée

typedef struct noeud{
  struct noeud * fg; // fils gauche
  struct noeud * fd; // fils droit
} noeud;

typedef struct arbre{
  struct noeud * root; // la racine
} arbre;


// on passe n en int * afin que n soit modifié par les appels recursifs
// cf cours sur les pointeurs
void card_rec(noeud * a,unsigned int * n){
  if (a->fg){ // si j'ai un fils gauche
    // j'ajoute à n le nombre de fils comptés à partir de fg
    card_rec(a->fg,n); 
  }  
  if (a->fg){ // si j'ai un fils droit
    // j'ajoute à n le nombre de fils comptés à partir de fd
    card_rec(a->fd,n); 
  }  
  ++ *n; // j'ajoute le noeud courant
}

unsigned int card(arbre  * a){
  // actuellement j'ai compté 0 noeuds, et je pars de la racine
  unsigned int res=0;
  card_rec(a->root,&res); 
  return res;
}

Bonne chance

badan · Answer

slt , j'ai le meme probleme , je trouve pas de koi apprendre cette recursivité, mais dernierement g téléchargé des fichiers pdf qui pourraient t'interesser, si tu es tjrs interssée : voici certains liens , sinn laisse ton email je te les enverrai.. bonne chance

http://www.math.u-psud.fr/~lichnew/spipE/rubrique.php3?id_rubrique=52

patnow · Answer

La récursivité (bis):

Je ne sais pas si ça peut encore servir mais bon, je me lance :

je vais essayer de vous traduire mon approche comme je le vois, en utilisant les pointeurs:

un fonction est de la forme: 
                                             fonction boucle(nœud)
                                             début
                                             Si {la racine est nulle} alors le résultat = 0
                                             sinon, on fait
                                                                 résultat = résultat + 1
                                                                 boucle(nœud_fils) 
                                             fin

- cette fonction commence à la racine;
- elle regarde si le premier nœud existe;
- s'il n'existe pas, la fonction renvoie le résultat à 0;
- sinon, il ajoute  +1 au résultat;
- et il recommence le même processus avec le nœud fils;
- s'il n'existe pas, alors le résultat est 1;
- sinon, il ajoute +1 au résultat précédent donc, le résultat = 2;
- et il recommence ainsi de suite jusqu'à un nœud_fils inexistant;

Ce qu'il faut comprendre, c'est que la première ligne de code nous dit que le résultat est nul si le nœud de l'arbre est inexistant. Or l'ordinateur comprend que la condition "résultat=0" n'est valable que pour le premier nœud ou le nœud racine. Donc, le résultat n'est pas réinitialisé quand un nœud fils existe. 

La fonction continuera alors sa boucle jusqu'à ce qu'il ne trouve plus de noeud fils.

J'espère avoir été assez clair et que j'ai aidé quelqu'un à comprendre quelque chose.
Bonne prog à tous!!!

[récursivité]

7 réponses

Discussions similaires