La récursion
Fermé
sarahh5126
Messages postés
5
Date d'inscription
samedi 11 novembre 2017
Statut
Membre
Dernière intervention
11 novembre 2017
-
11 nov. 2017 à 12:52
mamiemando Messages postés 33336 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 5 novembre 2024 - 14 nov. 2017 à 10:26
mamiemando Messages postés 33336 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 5 novembre 2024 - 14 nov. 2017 à 10:26
4 réponses
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
3 019
11 nov. 2017 à 12:55
11 nov. 2017 à 12:55
Bonjour,
Et où est le problème ? Tu as déjà tout décrit ce qu'il fallait faire...
Et où est le problème ? Tu as déjà tout décrit ce qu'il fallait faire...
sarahh5126
Messages postés
5
Date d'inscription
samedi 11 novembre 2017
Statut
Membre
Dernière intervention
11 novembre 2017
Modifié le 11 nov. 2017 à 13:01
Modifié le 11 nov. 2017 à 13:01
voilà mon programme, mais il affiche 26 fois c'est termine
#include <iostream> using namespace std; void fonction (char ) { char alphabet[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'}; int size=sizeof(alphabet); for(int i=0; i<size; i++) { if (alphabet[i]=!'Z') { cout<<alphabet[i]<<endl; fonction(alphabet[i]); cout<<alphabet[i++]<<endl; } else { cout<<"C'est terminee"<<endl; } } } int main() { char lettre; cout<<"Entrer une lettre en majuscule : "; cin>>lettre, fonction(lettre); return 0; }
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
3 019
11 nov. 2017 à 13:08
11 nov. 2017 à 13:08
void fonction (char )il n'a pas de nom ton paramètre de fonction ? Comment tu peux t'en servir du coup ?
int size=sizeof(alphabet);Tu as de la "chance" ici que ça fasse 26, mais sizeof ne sert pas à ça et la plupart du temps ça ne te donneras pas la valeur que tu penses.
for(int i=0; i<size; i++)Si tu as une boucle for ce n'est pas de la récursion...
if (alphabet[i]=!'Z')La comparaison "différent de" c'est
!=mais avec
=!tu fais une affectation du contraire, ce qui n'a pas beaucoup de sens...
sarahh5126
Messages postés
5
Date d'inscription
samedi 11 novembre 2017
Statut
Membre
Dernière intervention
11 novembre 2017
11 nov. 2017 à 13:12
11 nov. 2017 à 13:12
Alors, comment je peux régler ces pbs?
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
3 019
11 nov. 2017 à 13:17
11 nov. 2017 à 13:17
Reprends ton énoncé tel que tu l'as écrit dans ta question et code ni plus ni moins ce qui est marqué, tu n'as pas besoin d'avoir un tableau d'alphabet, de boucle for, etc. la réponse est beaucoup plus simple, il faut juste faire ça :
une fonction avec un seule argument qui est une lettre en majuscule
si la lettre est différente de "Z" il s'affiche cette lettre
et on fait l'appelle à cette fonction pour afficher les lettres qui viennent après
Si la lettre est "Z" il s'affiche que " c'est terminé"
sarahh5126
Messages postés
5
Date d'inscription
samedi 11 novembre 2017
Statut
Membre
Dernière intervention
11 novembre 2017
Modifié le 11 nov. 2017 à 13:25
Modifié le 11 nov. 2017 à 13:25
cette fois c'est une boucle infini .
// #include <iostream> using namespace std; void fonction (char alphabet) { /*char alphabet[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'}; int size=sizeof(alphabet); for(int i=0; i<size; i++) {*/ if (alphabet!='Z') { cout<<alphabet<<endl; fonction(alphabet); cout<<alphabet++<<endl; } else { cout<<"C'est terminee"<<endl; } //} } int main() { char lettre; cout<<"Entrer une lettre en majuscule : "; cin>>lettre, fonction(lettre); return 0; }
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
3 019
>
sarahh5126
Messages postés
5
Date d'inscription
samedi 11 novembre 2017
Statut
Membre
Dernière intervention
11 novembre 2017
11 nov. 2017 à 13:26
11 nov. 2017 à 13:26
C'est normal, puisque tu appelles fonction(alphabet); qui appelle fonction(alphabet); qui appelle fonction(alphabet); etc.
Si tu ne changes pas la valeur de alphabet ça ne va jamais s'arrêter...
Si tu ne changes pas la valeur de alphabet ça ne va jamais s'arrêter...
sarahh5126
Messages postés
5
Date d'inscription
samedi 11 novembre 2017
Statut
Membre
Dernière intervention
11 novembre 2017
11 nov. 2017 à 13:41
11 nov. 2017 à 13:41
Donc je dois introduire un vecteur alphabet qui contient les 26 lettres, non??
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
3 019
>
sarahh5126
Messages postés
5
Date d'inscription
samedi 11 novembre 2017
Statut
Membre
Dernière intervention
11 novembre 2017
11 nov. 2017 à 13:50
11 nov. 2017 à 13:50
Le C++ connait déjà les lettres...
char lettre = 'A'; std::cout << lettre; // A lettre++; std::cout << lettre; // B
mamiemando
Messages postés
33336
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
5 novembre 2024
7 801
14 nov. 2017 à 10:26
14 nov. 2017 à 10:26
Bonjour,
La théorie
Quand tu veux écrire une fonction récursive il faut :
1) déterminer quel(s) paramètre(s) de la fonction tu vas faire varier
2) choisir comment le faire évoluer
3) t'assurer que quelque soit la valeur initiale choisie, tu vas finir par atteindre le critère d'arrêt.
Imaginons que tu veuilles afficher une chaîne de caractère (
1) Ton paramètre récursif est le pointeur sur le caractère courant de la chaîne (
2) Tu veux lire la chaîne de gauche à droite. En C/C++ il suffit d'incrémenter
3) Tu vas t'arrêter dès que
On voit que, du moment que l'appel initial part au début de
Si par contre je décide de lire de droite à gauche, il n'y a aucune chance que je l'atteigne, et la fonction va moralement boucler à l'infini. Même si je pars à l'intérieur de
À travers cette explication on voit que le choix du critère d'arrêt (ici lire le caractère
On peut imaginer d'autres exemples de récursion plus compliqués.
Par exemple afficher chaque noeuds stockés dans une structure d'arbre binaire (un fils gauche un fils droit au plus). Dans cas tu vas par exemple entamer une récursion à partir d'un noeud racine. Tu vas à chaque fois vérifier si le noeud courant à un fils gauche (et seulement dans ce cas faire un appel récursif sur le fils gauche), et faire de même pour le fils droit s'il existe. On voit ici que l'on lit l'arbre de sa racine vers ses feuilles, qu'on finira par voir une et une seule fois chaque sommet de l'arbre, et que les appels récursifs cesseront une fois toutes les feuilles atteinte.
Imaginons le même problème avec une structure de graphe. C'est très proche de l'exemple précédent, sauf que la notion de fils est remplacée par la notion de noeuds voisins. La difficulté supplémentaire, c'est que rien n'interdit l'existence de cycle dans un graphe, ce qui entraînerait une boucle infinie. C'est la raison pour laquelle il va falloir marquer les sommets visités jusqu'ici et ne visiter un sommet que si celui-ci n'a pas été visité. Il faut donc passer en paramètre des appels récursifs un pointeur vers l'ensemble des sommets visités.
Retour à ton cas
Ton problème est extrêmement proche du premier exemple que j'ai donné. Personnellement je coderais même l'alphabet avec une chaîne de caractère, et dans ce cas il suffit de traduire ce que j'ai écrit en C/C++. Tu peux aussi rester sur une structure de tableau. Dans ce cas, il faudra comme tu le proposes maintenir l'index de ta lettre et t'assurer que tu n'as pas atteint le dernier index autorisé.
Pour revenir sur les histoires de
Bonne chance
La théorie
Quand tu veux écrire une fonction récursive il faut :
1) déterminer quel(s) paramètre(s) de la fonction tu vas faire varier
2) choisir comment le faire évoluer
3) t'assurer que quelque soit la valeur initiale choisie, tu vas finir par atteindre le critère d'arrêt.
Imaginons que tu veuilles afficher une chaîne de caractère (
const char *) terminée par le caractère
\0que je vais appeler
s.
1) Ton paramètre récursif est le pointeur sur le caractère courant de la chaîne (
const char *) que je vais appeler
pc. Cette chaîne est éventuellement vide (le premier caractère est alors '\0').
2) Tu veux lire la chaîne de gauche à droite. En C/C++ il suffit d'incrémenter
pc.
3) Tu vas t'arrêter dès que
pcpointe sur
\0.
On voit que, du moment que l'appel initial part au début de
s, ou quelque part entre le début et la fin de
s, cette fonction finira par atteindre le caractère
\0de
s.
Si par contre je décide de lire de droite à gauche, il n'y a aucune chance que je l'atteigne, et la fonction va moralement boucler à l'infini. Même si je pars à l'intérieur de
s, mon curseur va déborder de s par la gauche et commencer à lire en dehors de
s... ce qui va déclencher rapidement une erreur de segmentation.
À travers cette explication on voit que le choix du critère d'arrêt (ici lire le caractère
\0) et la manière dont on fait la récursion est importante.
On peut imaginer d'autres exemples de récursion plus compliqués.
Par exemple afficher chaque noeuds stockés dans une structure d'arbre binaire (un fils gauche un fils droit au plus). Dans cas tu vas par exemple entamer une récursion à partir d'un noeud racine. Tu vas à chaque fois vérifier si le noeud courant à un fils gauche (et seulement dans ce cas faire un appel récursif sur le fils gauche), et faire de même pour le fils droit s'il existe. On voit ici que l'on lit l'arbre de sa racine vers ses feuilles, qu'on finira par voir une et une seule fois chaque sommet de l'arbre, et que les appels récursifs cesseront une fois toutes les feuilles atteinte.
Imaginons le même problème avec une structure de graphe. C'est très proche de l'exemple précédent, sauf que la notion de fils est remplacée par la notion de noeuds voisins. La difficulté supplémentaire, c'est que rien n'interdit l'existence de cycle dans un graphe, ce qui entraînerait une boucle infinie. C'est la raison pour laquelle il va falloir marquer les sommets visités jusqu'ici et ne visiter un sommet que si celui-ci n'a pas été visité. Il faut donc passer en paramètre des appels récursifs un pointeur vers l'ensemble des sommets visités.
Retour à ton cas
Ton problème est extrêmement proche du premier exemple que j'ai donné. Personnellement je coderais même l'alphabet avec une chaîne de caractère, et dans ce cas il suffit de traduire ce que j'ai écrit en C/C++. Tu peux aussi rester sur une structure de tableau. Dans ce cas, il faudra comme tu le proposes maintenir l'index de ta lettre et t'assurer que tu n'as pas atteint le dernier index autorisé.
Pour revenir sur les histoires de
sizeof, cette fonction retourne la taille en octets de la variable ou du type passé en paramètre. Par chance
charfait 1 octet et ton tableau a 26 cases, soit une taille de 26 octets. Donc ça marche. Mais comme on te l'a dit, il faut être prudent. Par exemple si tu devais résoudre le même problème pour traiter des caractères cyrilliques ou chinois par exemple, tu utiliserais par exemple des
wchar_tqui font deux octets. Du coup sizeof te renverrait une taille faisant 2 fois la taille de ton alphabet. En tout rigueur il faudrait donc diviser la taille du tableau par la taille d'une cellule.
Bonne chance