Tutorial récursivité problème

Bonjour, j'ai préféré faire un autre topic car il est un peu différent de celui que j'ai il y a qq heurs.

En retravaillant la procédure combinaison :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

procedure combinaison2(st, tete: string); var i: integer; begin if length(st) = 1 then memo1.lines.add(tete + st) else for i := 1 to length(st) do begin combinaison1(copy(st, 2, length(st) - 1), tete + st[1]); st := copy(st, 2, length(st) - 1) + st[1]; end; end;

---

et en retravaillant le déroulement schématisé :
http://recursivite.developpez.com/?page=page_1#L0

Je n'arriver pas a dérouler de la même manière :
Ici le

Code:

---

length(st) - 1

---

ne me semble pas correct car au 1er appel de la procédure , je me retrouve avec :

Code:

---

combinaison('b', 'a')

---

et non

Code:

---

combinaison('bc', 'a')

---

??

Est ce qqun pourrait me dire ou est ce que je me suis tromper ?

Juste pour rajouter pour moi le code qui "marche" en accord avec le schéma
est le suivant :

JE l'ai tourné dans tous les sens et j'arrive à qqch de marche en accord avec le corps avec ce code :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

procedure combinaison2(st, tete: string); var i: integer; begin if length(st) = 1 then memo1.lines.add(tete + st) else for i := 1 to length(st) do begin combinaison1(copy(st, 2, length(st) ), tete + st[1]); st := copy(st, 2, length(st) ) + st[1]; end; end;

---

Y aurait-il des erreurs ?

Pourrais-tu nous dire ce que tu cherches à faire exactement ? S'agit-il de trouver toutes les combinaisons d'une ensemble de caractères donnés ?

cdlt

Oui sans le role extact de la fonction c'est dure de deviner tout seul ... surtout avec un code incomplet ;)

D'ailleur je le redit : Tu parle de recursivitée mais en aucun cas cette fonction telle qu'elle est recursive.
Le but premier d'une fonction recursive est de s'auto-appeler, or je ne vois aucun appel a "Combinaison2" ..... Par contre il y a une fonction "Combinaison1" dont le code serait fort utile pour comprendre le fonctionnement de ta procedure ;)

J'ai un doute, cela ressemble très fortement au post de Bativir :

http://www.developpez.net/forums/sho...d.php?t=336892

Aurait-on affaire à une joyeuse bande d'étudiants en mal s'inspiration ? Est-on en période d'examen ?

Prière de réfléchir un peu avant de poser des questions (si mon doute est confirmé).

cdlt

Bon je crois que je ne me suis pas bien fait comprendre :cry: .....
Je débute en récursivité.
Qu'est ce que je fait: je vais directement vers le cours proposé par Developpez.com .
Je suis le cours pas à pas , je me teste pour savoir si j'ai bien acquis les connaissance ou pas.
Et la en faisant des tests , je m'aperçois qu'il y a qqch qui ne va pas.
Le problème est que le schéma de déroulement ne me semble pas en accord avec le code proposé : Voir la partie du bas .
http://recursivite.developpez.com/?page=page_1

Pour moi le bon code serait :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

procedure combinaison2(st, tete: string); var i: integer; begin if length(st) = 1 then memo1.lines.add(tete + st) else for i := 1 to length(st) do begin combinaison1(copy(st, 2, length(st) ), tete + st[1]); st := copy(st, 2, length(st) ) + st[1]; end; end;

---

Citation:

---

Aurait-on affaire à une joyeuse bande d'étudiants en mal s'inspiration ? Est-on en période d'examen ?

Prière de réfléchir un peu avant de poser des questions (si mon doute est confirmé).

---

Ton doute proviendrai peut être d'un manque d'humilité et de compassion vis à vis de débutants.

Citation:

---

Oui sans le role extact de la fonction c'est dure de deviner tout seul ... surtout avec un code incomplet

D'ailleur je le redit : Tu parle de recursivitée mais en aucun cas cette fonction telle qu'elle est recursive.
Le but premier d'une fonction recursive est de s'auto-appeler, or je ne vois aucun appel a "Combinaison2" ..... Par contre il y a une fonction "Combinaison1" dont le code serait fort utile pour comprendre le fonctionnement de ta procedure

---

Dans le cours proposé par developper.com c'est marqué récursivité:
Je pense que combinaison1 est la meme que combinaison2: c'est juste pour dire que c'est comme si on avait une autre fonction qui fait un autre programme...:)

Citation:

---

Envoyé par bdptaki

Ton doute proviendrai peut être d'un manque d'humilité et de compassion vis à vis de débutants.

---

Pas vraiment, on observe cependant parfois des vagues de demandes identiques et "douteuses" qui transpirent le travail à rendre, je n'approuve pas cette méthode car elle dévoie l'objectif du travail de l'étudiant et l'incite à choisir la voie de la facilité. Ceci dit, visiblement ta démarche semble sérieuse.

Merci pour ta constatation,

Pour revenir à notre sujet, je suis entrain d'avancer dans mon apprentissage de la récursivité, mais je ne dois laisser aucun coin d'ombre, sinon je pourrai passer à coté de qqch d'essentiel

Citation:

---

Pas vraiment, on observe cependant parfois des vagues de demandes identiques et "douteuses" qui transpirent le travail à rendre, je n'approuve pas cette méthode car elle dévoie l'objectif du travail de l'étudiant et l'incite à choisir la voie de la facilité.

---

Tout a fait d'accord avec toi.
Par contre j'emet un certain bemol : Quand on parle de "travail a rendre" ou encore de TD, ca n'explu pas le fait de charcher des information, que ce soit a la BU sur des bouqins, sur des sites internet, aupres du Prof pour comprendre certains points ..... et pourquoi pas aupres des nombeux developeurs professionnels qui transite par ce forum.

Totu depends de la facon dont les choses sont posées. Un TD ne doit pas etre "fait" par les autres membre mais quand il s'agit comme ici de question de comprehension ou d'analyse d'un code produit par l'eleve, je ne vois pas le probleme.
Enfin ca depends des profs, mais pour moi, ca montre sa capacite de recherche face a un probleme, gros avantage dans le metier de la prog. Le tout est que ce qu'il a code il l'a compris. Peut importe le moyen qu'il a pris pour acquerir cette competence :)

LE tout est de rester dans le domaine de l'apprentissage et non de l'assistanat.

Pour ce qui est de ton probleme de recursivité, je vais essayer de te donner quelques pistes.

LE principe de la recursivitee est de reperer dans u nalgorithme un "schema" redondant sur lequel baser son traitement.
Ici le schema de creation d'un anagrame est un arbre qui consite a prendre chacune des lettres du mot et de lui concatener les differents anagrames des lettres qui restent.
Donc au niveaux Zero, on a pour CLORISH 7 possibilité :
C+Anagrame(LORISH);
L+Anagrame(CORISH);
O+Anagrame(CLRISH);
R+Anagrame(CLOISH);
I+Anagrame(CLORSH);
S+Anagrame(CLORIH);
H+Anagrame(CLORIS);

On a donc besoin de 2 variables qui seront medifiee dans le temps : Tete et Str. Str etant le reste des lettres et Tete le debut de l'anagrame.

L'algo est donc :

Code:

---

1 2 3 4 5 6 7

Procedure Anagrame :: (Str, String), (Tete : String) Pour tout i alant de 1 a Taille(Str) faire Retirer Str[i] a Str Ajouter Str[i] a la fin de tete; Appel Anagrame(Str, Tete) Fin Pour

---

DE cette maniere, les appels successifs seront :
Appel(0)-i(0) : Str : 'CLORISH' - Tete : '';
Appel(1)-i(0) : Str : 'ORISH' - Tete : 'CL';
Appel(2)-i(0) : Str : 'RISH' - Tete : 'CLO';
Appel(3)-i(0) : Str : 'ISH' - Tete : 'CLOR';
Appel(4)-i(0) : Str : 'SH' - Tete : 'CLORI';
Etc ....

[Pause repas : LA fin tout a l'heure ;)]

[Retour de pause]

Donc si on considere l'algo precedent, Dans le premier appel a Anagrame('CLORISH', '') on entre dans la boucle for et on lance Anagrame('ORISH', 'C') ce qui met en pause l'execution de l'appel precedent, le temps que cet appel soit fini. Or cet appel ne sera fini qu'apres la fin de la boucle for, c'est a dire apres avoir calculé tous les Anagrames commencant par 'CL*****' jusqu'a 'CH******'.

De meme, le calcule de lanagrame de 'CL*****' ne se terminera qu'apres le calcul des anagrames de 'CLO****' a 'CLH****'

Et ainsi de suite.
Il faut donc s'arreter a un moment pour que l'on puisse finir un calcul qui entrainera le depart du calcul de l'anagrame suivant dans la boucle d'appel, et petit a petit finir chacune des procedures et rendre la main au programme.

Cette procedure d'arret intervien avec un test de finalité.
Ici c'est :

Code:

---

Si Taille(Str) = 1 alors Validation de l'anagrame tete+Str

---

Ne faisant plus appel a la procedure Anagrame, on peut finir la procedure en cours et remonter a l'appel precedant.

Anagrame('SH', 'CLORI') lance le cacul suivant :
i=0 => Anagrame('H', 'CLORIS') qui se termine et donne 'CLORISH'
i=1 => Anagrame('S', 'CLORIH') qui se termine et donne 'CLORIHS'

Si on remonte un coup plus haut :
Anagrame('ISH', 'CLOR') a lancé les calculs suivant :
i=0 => Anagrame('SH', 'CLORI') qui on le sait se termine en donnant 'CLORISH' et 'CLORIHS'
i=1 => Anagrame('IH', 'CLORS' qui se terminera en donnat 'CLORSIH' et 'CLORSHI'
i=2 => Anagrame ('IS', 'CLORH') qui se terminsera en donnat 'CLORHIS' et 'CLORHSI'

ET ainsi de suite .... jusqu'a ce que l'arbre soit parcouru entierement ....

Des questions ?!? ;)

ok, ok :D merci pour l'explication, je vais étudier tout sa, et s'il y a.....

Merci pour ton déroulement

DE rien .... mais si je peux te donner un dernier conseil : Prends une feuille de papier et parcours ton code ligne par ligne en notant sur le papier l'etat des variables cree ou non et leur valeurs.
Ca va t'aider a comprendre comment tourne les algo.