Menu

La récursion

sarahh5126 5 Messages postés samedi 11 novembre 2017Date d'inscription 11 novembre 2017 Dernière intervention - 11 nov. 2017 à 12:52 - Dernière réponse : mamiemando 28408 Messages postés jeudi 12 mai 2005Date d'inscriptionModérateurStatut 19 juin 2018 Dernière intervention
- 14 nov. 2017 à 10:26
Bonjour à tous,
Je suis débutante en c++ ,et je veux faire une démonstration de la récursion,
Je veux définir 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é"
Mercii d'avance.
Afficher la suite 

Votre réponse

10 réponses

KX 15557 Messages postés samedi 31 mai 2008Date d'inscriptionModérateurStatut 18 juin 2018 Dernière intervention - 11 nov. 2017 à 12:55
0
Merci
Bonjour,

Et où est le problème ? Tu as déjà tout décrit ce qu'il fallait faire...
Commenter la réponse de KX
sarahh5126 5 Messages postés samedi 11 novembre 2017Date d'inscription 11 novembre 2017 Dernière intervention - Modifié par KX le 11/11/2017 à 13:01
0
Merci
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 15557 Messages postés samedi 31 mai 2008Date d'inscriptionModérateurStatut 18 juin 2018 Dernière intervention - 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...
Commenter la réponse de sarahh5126
sarahh5126 5 Messages postés samedi 11 novembre 2017Date d'inscription 11 novembre 2017 Dernière intervention - 11 nov. 2017 à 13:12
0
Merci
Alors, comment je peux régler ces pbs?
KX 15557 Messages postés samedi 31 mai 2008Date d'inscriptionModérateurStatut 18 juin 2018 Dernière intervention - 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 5 Messages postés samedi 11 novembre 2017Date d'inscription 11 novembre 2017 Dernière intervention - 11 nov. 2017 à 13:24
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 15557 Messages postés samedi 31 mai 2008Date d'inscriptionModérateurStatut 18 juin 2018 Dernière intervention > sarahh5126 5 Messages postés samedi 11 novembre 2017Date d'inscription 11 novembre 2017 Dernière intervention - 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...
sarahh5126 5 Messages postés samedi 11 novembre 2017Date d'inscription 11 novembre 2017 Dernière intervention - 11 nov. 2017 à 13:41
Donc je dois introduire un vecteur alphabet qui contient les 26 lettres, non??
KX 15557 Messages postés samedi 31 mai 2008Date d'inscriptionModérateurStatut 18 juin 2018 Dernière intervention > sarahh5126 5 Messages postés samedi 11 novembre 2017Date d'inscription 11 novembre 2017 Dernière intervention - 11 nov. 2017 à 13:50
Le C++ connait déjà les lettres...

char lettre = 'A';
std::cout << lettre; // A
lettre++;
std::cout << lettre; // B
Commenter la réponse de sarahh5126
mamiemando 28408 Messages postés jeudi 12 mai 2005Date d'inscriptionModérateurStatut 19 juin 2018 Dernière intervention - 14 nov. 2017 à 10:26
0
Merci
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 (
const char *
) terminée par le caractère
\0
que 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
pc
pointe 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
\0
de
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
char
fait 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_t
qui 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
Commenter la réponse de mamiemando