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.

Salut,

Tu viens d'expliquer clairement ton problème, tu connais sûrement les bases, donc la création de fonctions, l'utilisation de std::string, le passage d'argument à fonction. Où est le problème dans ce cas ?

voici mon programme ,

//

#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;

            alphabet[i++]

            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;

}

C'est normal qu'il ne marche pas. Par contre à l'avenir, met ton code dans un bloc de code, et explique le problème. Là je l'ai vu très vite, mais j'ai dû prendre la peine de chercher. D'autres ne le feraient pas.

Quand tu déclares ta fonction, tu prends un char en argument, mais tu ne le nommes pas, donc tu ne peux pas le récupérer et l'utiliser. Ton for quand tu parcours l'alphabet commece à int i=0; il devrait commencer à (pseudo code, attention) : int i=index_of(lettre, alphabet).

#include <iostream>

void fonction(char lettre)
{
    if (lettre != 'Z')
    {
        std::cout << lettre << std::endl;
        fonction(++lettre);
    }
    else
        std::cout << "Z" << std::endl << "terminé" << std::endl;
}
int main()
{
    char lettre;
    std::cout << "Entrer une lettre en majuscule : ";
    std::cin >> lettre,
    fonction(lettre);
    return 0;

}

un char n'est qu'un nombre

EDIT: j'ai viré using namespace std;

-
Edité par Anonyme 11 novembre 2017 à 15:08:54

@Yaalval : utiliser "using namespace std" est une mauvaise pratique (raison + que faire).

@Ksass`Peuk oui je sais bien, je l'ai laissé dans le code parce qu'elle l'utilisait (c'est ce que j'essaie de faire comprendre à mes profs, mais ils trouvent qu'écrire std::cout est, je cite "syntaxiquement lourd", et que les namespaces "c'est une fonctionnalité inutile pour nous")

Yaalval a écrit:

oui je sais bien, je l'ai laissé dans le code parce qu'elle l'utilisait

Pour le coup sur le forum, on essaie toujours de rectifier le tir parce qu'ici le but n'est pas de faire plaisir au profs mais d'être le plus propre possible .

Yaalval a écrit:

(mais ils trouvent qu'écrire std::cout est, je cite "syntaxiquement lourd", et que les namespaces "c'est une fonctionnalité inutile pour nous")

On pourrait se demander pourquoi ils ont choisi C++ alors si ces deux arguments sont importants pour eux.

D'accord, dans ce cas je corrige

Excellente question à laquelle je n'ai d'autre réponse que "le C++ est très utilisé en entreprise" (je cite notre professeur de CM d'informatique). C'est vraiment dommage, surtout quand on voit la qualité du cours (notre cours est en français, basé sur un excellent cours en anglais de cppreference, mais en le traduisant ils ont remodelé pas mal le truc pas dans le bon sens à mon goût).

Yaalval a écrit:

D'accord, dans ce cas je corrige

Excellente question à laquelle je n'ai d'autre réponse que "le C++ est très utilisé en entreprise" (je cite notre professeur de CM d'informatique). C'est vraiment dommage, surtout quand on voit la qualité du cours (notre cours est en français, basé sur un excellent cours en anglais de cppreference, mais en le traduisant ils ont remodelé pas mal le truc pas dans le bon sens à mon goût).

Envoie nous tes profs, on se fera un plaisir de leur (tapper dessus :p) donner de vraie explications

-
Edité par Deedolith 11 novembre 2017 à 18:35:26

merci pour vous, j'ai réglé le problème.

//

#include <iostream>

using namespace std;

void fonction(char alphabet)

{

        if (alphabet!='Z')

        {

            cout<<alphabet<<endl;

            fonction(++alphabet);

        }

        else

        {

           cout<<"C'est terminee"<<endl;

        }

    }

int main()

{

    char lettre[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(lettre);

    cout<<"Entrer une lettre en majuscule : "<<endl;

    for(int i=0; i<size; i++)

    {

    cin>>lettre;

    fonction(lettre[i]);

    }

    return 0;

}

Salut,

La règle, quand tu veux aborder la récursion, c'est de trouver ce que l'on appelle le  "cas de base".  C'est la situation dans laquelle ta fonction ne sera pas appelée une fois de plus.

L'idée est alors de commencer par gérer ce cas de base (on trouve généralement un return dedans) et de faire en sorte que toute la logique qui suit le cas de base tende à y retourner.

Dans ton cas, le cas de base, c'est que la lettre est égale à z, si bien que ta fonction devrait prendre la forme de

void function(char c){
   if(c == 'z){
       std::cout<<c<<"... Termine\n";
       return;
   }
   std::cout<<c<<" ";
   function(++c);
}

Ceci étant dit, il faut savoir que l'on pourrait remplacer à peu près n'importe quelle boucle par une fonction récursive, mais que c'est rarement une bonne idée: si tu peux -- sans trop compliquer ta logique -- avoir recours à une boucle, tu as très largement intérêt à utiliser la boucle plutôt que la récursivité.

Dans quelques cas (les tours de Hannoï, par exemple), on se trouve dans l'impossibilité -- ou du moins face à un exercice particulièrement difficile -- de fournir une logique adéquate sans passer par la récursivité.  Et nous n'aurons alors pas d'autre choix que d'y avoir recours.

Il faudrait idéalement limiter l'utilisation de la récursivité à ces cas pour lesquels nous n'avons pas d'autre choix, car il s'agit d'une possibilité de "haut niveau" qui arrive avec une série de problème, dont -- entre autres -- le fait que la récursivité a rapidement tendance à surcharger la pile d'appels.

Si bien que l'exercice que tu essayes de remplir, le calcul de exponentielle ou de la factorielle ne sont pas des excercices qui méritent d'avoir recours à la récurisivité, car il est tout à fait possible de s'en sortir avec une simple boucle

Super ! Je me posais tout un tas de questions justement. Merci pour cette explication@koala01.

Sinon j'ai une question, si l'on fait ça :

void f(char c)
{
    if(c != 'Z'){
        std::cout << c << '\n';
        return f(++c);
    }
    std::cout << 'Z' << " end" << '\n';
}

C'est sans danger de renvoyer la fonction ainsi ? Ou il y peut éventuellement y avoir quelques soucis selon les arguments par exemple ?

-
Edité par Guit0Xx 11 novembre 2017 à 21:53:19

Comme je l'ai dit, la règle impérative est d'arriver à identifier et à isoler le cas de base.

A partir de là, tu fais comme tu veux, bien sur...  Mais... il faut comprendre qu'il y certaines circonstances dans lesquelles il y a "plusieurs cas de base".

Alors, ce n'est que mon avis personnel, mais, il me semble qu'il est plus facile de commencer par isoler les différents cas de base auxquels tu es confronté pour "les avoir hors du chemin" avant de t'inquiéter de la logique qui permettra d'y arriver.

Maintenant, on entre vraiment dans une logique qui consiste à faire les choses de la manière la plus simple possible (qui devrait toujours être l'objectif final, en sommes), et en ce qui la concerne... chacun voit midi à sa porte.

Alors, le problème n'est pas tant dans l'utilisation de paramètres: du moment que tu les transmets dans le bon ordre, tu n'auras pas de problème à travailler d'une manière plutôt que d'une autre. Le véritable problème, vient de l'utilisation que tu feras des différents paramètres, et ca, seule une logique implacable te permettra de t'en sortir

koala01 a écrit:

Alors, le problème n'est pas tant dans l'utilisation de paramètres: du moment que tu les transmets dans le bon ordre, tu n'auras pas de problème à travailler d'une manière plutôt que d'une autre. Le véritable problème, vient de l'utilisation que tu feras des différents paramètres, et ca, seule une logique implacable te permettra de t'en sortir

Héhé, ok je vois. Merci 

Bonjour.

D'expérience, la récursion en C++ est surtout un bon moyen de se prendre la tête et de faire stack overflow si les appels récursifs sont de forte profondeur. Une bien meilleure pratique est d'utiliser une boucle while. Néamoins, à des fins didactiques, et pour le jour ou t'écriras du code avec des variadic templates, c'est important que tu connaisse le principe de la récursion, et donc que tu bosses un peu sur ton exemple.


Si tu relis la manière dont tu as posé ton problème, il y a déja une erreur. Ta fonction ne peut pas prendre en paramètre seulement UNE LETTRE, et avoir dans son code un truc du genre "Lettre suivante". Je pense que ta focntion dont prendre en paramètre un pointeur sur une lettre (pour pouvoir l'incrémenter et passer a la lettre suivante), ou bien un tableau de lettre, et un index (pour connaitre la lettre en cours, et pouvoir passer a la lettre suivante).

Guit0Xx a écrit:

void f(char c)
{
    if(c != 'Z'){
        std::cout << c << '\n';
        return f(++c);
    }
    std::cout << 'Z' << " end" << '\n';
}

C'est sans danger de renvoyer la fonction ainsi ? Ou il y peut éventuellement y avoir quelques soucis selon les arguments par exemple ?

Je sais pas ce que tu veux dire par "renvoyer la fonction", mais celle-ci peut en effet poser soucis. Si on utilise cette fonction en fournissant un argument supérieur à 'Z' (appel de f('Z'+1) par exemple), la fonction ne vérifie pas ce cas et donc on va calculer indéfiniment (réellement je pense qu'on fait un overflow et donc on va retomber sur 'Z' au bout d'un moment, et encore plus réellement je pense qu'on aura rempli la pile d'appel avant d'atteindre 'Z')

#include <string>
#include <iostream>

//--- AVEC LA RECURSION (crade) ---

void f(const std::string &s, size_t pos){
	//on vérifie que la chaine ne soit pas terminée
	if(pos >= s.size() ){
		std::cout << "fin de chaine atteinte\n";
		return;
	}

	//on teste le caractère actuel
	const char c = s[pos];
	if(c=='Z'){
		//Z : j'affiche un message et je termine
		std::cout << "Z trouvé à la position " << pos<<"\n";
		return;
	}else{
		//pas Z : récursion : j'appelle f à la position suivante
		f(s, pos+1);
	}
}

int main(){
	f("Banane",0);//	fin de chaine atteinte
	f("caZ",0);//Z trouvé à la position 2
	f("ZZZ",0);//Z trouvé à la position 0
}

#include <string>
#include <iostream>

//--- Avec une boucle (propre) ---

void f(const std::string &s){


	for(size_t i=0; i < s.size() ; ++i){
		const char c = s[i];
		if(c=='Z'){
			//Z : j'affiche un message et je termine
			std::cout << "Z trouvé à la position " << i<<"\n";
			return;
		}
	}

	std::cout << "fin de chaine atteinte\n";
}

int main(){
	f("Banane");//	fin de chaine atteinte
	f("caZ");//Z trouvé à la position 2
	f("ZZZ");//Z trouvé à la position 0
}

Je pense a voir tes commentaires qu'il te maques quelques bases en C++, commences par plus simple.

Pour info voila ce que fait la lignereturn f(++c);

++c incrémente la valeur de c. comme les caractères sont des nombres, ca ajoute 1 au nombre. Ca ne prend PAS DU TOUT le caractère suivant dans une chaîne de caractère.

f(++c), va donc incrémenter c, puis appeler f sur la nouvelle valeur de c.

f ne renvoie rien, la ligne return f(quelquechose) ne va pas compiler, parce que return s'attend à avoir quelque chose à retourner.

-
Edité par ledemonboiteux 13 novembre 2017 à 11:35:03

ledemonboiteux a écrit:

D'expérience, la récursion en C++ est surtout un bon moyen de se prendre la tête et de faire stack overflow si les appels récursifs sont de forte profondeur. Une bien meilleure pratique est d'utiliser une boucle while.

Le mieux c'est encore d'écrire la version qui est la plus expressive. Si le compilateur est trop mal branlé pour dé-récursiver du tail-recursive, il sera toujours temps de changer ça par une boucle plus tard.

Dans la pratique, j'ai eu des tas de problème avec cette stratégie (notamment quand je voulais détruire des arbres et qu'il y avait des cascades de destructeurs). C'est en vrai très risqué car on parie sur une fonctionnalité du compilateur qui dépend du compilateur, du niveau d'optimisation, de la taille de la pile et de la taille des données à l'exécution.

Ca fait des bugs très traîtres et difficiles à trouver, parce que le code d'exemple et de tests sur de petits niveaux de récursion va marcher, alors que celui sur de grands niveau de récursion (donc très souvent dans les cas concrêts rares), va planter mystérieusement, sur des cas particuliers, de versions particulières de compilateuirs, avec des paramètres d'optimisation particuliers.

Je préconiserai plutot un stratégie du type :
- J'ai la preuve que mon niveau de récursion est borné et petit : => on fait ce qui est le plus expressif
- Je n'ai pas cette preuve : boucle.

Pour faire ce que tu dis, il faut a minima aller vérifier dans goldbot l'assembleur, et s'assurer que le compilateur qu'on utlise, avec les paramètres qu'on utilise, va optimiser la récursion en écrivant lui même la boucle. C'est un peu chiant quand même.

Oui enfin si le remplacement de la pile d'appel, c'est une dérécursivation à la main avec une structure de données qui sert de pile explicite, on n'a pas supprimé le problème de débordement.

Dans ce cas, on commence par repousser la limite de taille de la pile, avec les systèmes qui le permettent.  uname -s nnn, sous Linux/Bash.

Changer la taille de la pile est une solution pire : ca va la changer pour tous les threads et toutes les piles.

Si plus tard ton code utilise de nombreux threads (ce qui 'nest pas une très bonne pratique non plus), ca va consommer beaucoup de mémoire pour rien.

Avec la stratégie de la boucle, on consomme de la mémoire, en dehors de la pile, uniquement lorsque c'est nécessaire.

Encore une fois, on en revient à ce que je disais au tout début: la récursivité ne doit être envisagée que lorsqu'il est beaucoup plus compliqué d'exprimer une logique identique sous la forme d'une boucle.

Si tu peux avoir une boucle du genre de

Type * ptr = firstNode;
while(ptr){
    Type * next = ptr->next;
    delete ptr;
    ptr= next;
}

tu n'as -- a priori -- pas énormément de raison de passer par la récursivité.

ledemonboiteux a écrit:

Changer la taille de la pile est une solution pire : ca va la changer pour tous les threads et toutes les piles.

Si plus tard ton code utilise de nombreux threads (ce qui 'nest pas une très bonne pratique non plus), ca va consommer beaucoup de mémoire pour rien.

Avec la stratégie de la boucle, on consomme de la mémoire, en dehors de la pile, uniquement lorsque c'est nécessaire.

Houla. Faut revenir aux réalités du système...

1) ça ne change pas la taille de la pile, ça change la _limite_ de la taille de la pile. Ca ne prend pas plus de place que ce qu'on en consomme réellement (arrondi à la taille de page immédiatement supérieure).

2) Dans un système d'exploitation moderne, l'espace de la pile (ou de tout autre segment) n'est pas alloué au départ, il l'est au fur à mesure des besoins (c'est un truc qui repose sur les protections mémoires et les tables de pages : quand est détecté un accès en dehors de l'espace alloué, ça déclenche une extension du segment par modification de la table des pages - si la limite n'est pas atteinte).

3) ce n'est pas parce que plusieurs = N threads ont accès à un même espace que l'espace utilisé est multiplié par N.  Déjà si c'est un espace partagé, il n'y a qu'un exemplaire. Ensuite, quand ce sont des copies, il y a la notion de COW (copy on write) qui intervient. La copie effective d'une page n'est faite qu'au moment où la page partagée est modifiée (le processus acquiert alors une "copie personnelle"). La plupart du temps, ça n'alloue rien de plus.

Donc ça ne consomme pas plus de place que ça n'en n'a besoin. Et personne n'a parlé de faire de multiples threads dans un truc récursif qui exploserait la pile. Faut pas partir en vrille.

#include <string>
#include <iostream>
#include <deque>

template<typename T>
struct Recursive_node{
	template<typename... Args>
	Recursive_node(Args...a): data(std::forward<Args>(a)...), next(nullptr) {++created;}

	template<typename... Args>
	Recursive_node * push(Args... a){
		next=new Recursive_node<T>(std::forward<Args>(a)...);
		return next;
	}

	~Recursive_node(){
		delete next;
		++deleted;
	}

	T data;
	Recursive_node<T>*next=nullptr;

	static size_t created;
	static size_t deleted;

};

template<typename T> size_t Recursive_node<T>::created=0;
template<typename T> size_t Recursive_node<T>::deleted=0;





//--- idem but with a while loop ---

template<typename T>
struct Loop_node{
	template<typename... Args>
	Loop_node(Args...a): data(std::forward<Args>(a)...), next(nullptr) {++created;}

	template<typename... Args>
	Loop_node * push(Args... a){
		next=new Loop_node<T>(std::forward<Args>(a)...);
		return next;
	}

	~Loop_node(){
		++deleted;
	    if(next!=nullptr){
	    	std::deque<Loop_node*> delete_latter;
	    	Loop_node<T>*c=this;
	    	Loop_node<T>*n=next;
	    	while(n!=nullptr){
	    		delete_latter.push_back(n);
	    		c->next=nullptr;
	    		c=n;
	    		n=n->next;
			}

	    	for(Loop_node<T>*d:delete_latter){delete d;}
	    }
	}

	T data;
	Loop_node<T>*next=nullptr;

	static size_t created;
	static size_t deleted;

};
template<typename T> size_t Loop_node<T>::created=0;
template<typename T> size_t Loop_node<T>::deleted=0;








int main(){

	typedef Loop_node<size_t> Node_t;

	{
		Node_t n(0);
		//--- chain 1 000 000 nodes => segmentation fault gcc -O3 ---
		Node_t * push_here=&n;
		for(size_t i=1; i<1000000;++i){
			push_here=push_here->push(i);
		}
	}

	std::cout << "created:" << Node_t::created <<"\n";
	std::cout << "deleted:" << Node_t::deleted <<std::endl;



}

J'ai fait un peu de code de test :

sur 100 000 noeuds : 0.018s pour la version avec la boucle, et 0.022s pour la version avec la récursion
sur 1 000 000 de noeuds : 0.126s pour la version avec la boucle et segfault pour la version avec la récursion.

J'ai compilé avec g++ -O3

Je n'ai pas changé la taille de la pile.

Je ne sais pas comment on monitore proprement la mémoire vive utilisée au pic de consommation, mais je testerai bien pour voir.

Et le meilleur  des deux mondes : pas de récursion, pas de pile :

//--- idem but with a while loop AND NO STACK ---

template<typename T>
struct Loop_node2{
	template<typename... Args>
	Loop_node2(Args...a): data(std::forward<Args>(a)...), next(nullptr) {++created;}

	template<typename... Args>
	Loop_node2 * push(Args... a){
		next=new Loop_node2<T>(std::forward<Args>(a)...);
		return next;
	}

	~Loop_node2(){
		++deleted;
		Loop_node2 * c = this->next;
		while(c!=nullptr){
			Loop_node2<T>*n=c->next;
			c->next=nullptr;
			delete c;
			c=n;
		}
	}


	void delete_r(Loop_node<T>* m){

	}


	T data;
	Loop_node2<T>*next=nullptr;

	static size_t created;
	static size_t deleted;

};
template<typename T> size_t Loop_node2<T>::created=0;
template<typename T> size_t Loop_node2<T>::deleted=0;





int main(){

	typedef Loop_node2<size_t> Node_t;

	{
		Node_t n(0);
		//--- chain 1 000 000 nodes => segmentation fault gcc -O3 ---
		Node_t * push_here=&n;
		for(size_t i=1; i<1000000;++i){
			push_here=push_here->push(i);
		}
	}

	std::cout << "created:" << Node_t::created <<"\n";
	std::cout << "deleted:" << Node_t::deleted <<std::endl;



}

-
Edité par ledemonboiteux 20 novembre 2017 à 16:56:31

Le destructeur n'est pas tail-recursif (puis que la désallocation intervient nécessairement après la complétion du corps du destructeur appelé), donc évidemment pas optimisé pour une tail-recursion.

-
Edité par Ksass`Peuk 20 novembre 2017 à 16:42:28

Et encore, ton destructeur de Loop_node n'a absolument pas besoin d'être aussi complexe!  Tu fais pas mal de travail pour rien, vu qu'il suffit d'un

Loop_node::~Loop_node(){
    while(next){
        auto * temp=next->temp;
        delete next;
        ++deleted;
        next=temp;
    }
}

Tu n'as absolument aucune raison de passer par le fait de remplir une collection (quelle qu'elle soit) de pointeur pour pouvoir créer ta boucle

EDIT: quant au Recursive_node, son destructeur devrait être proche de

Recursive_node::~Recursive_node(){
    if(next)
        delete next;
}

Ce 'est pas parce que delete est garanti sans effet lorsque le pointeur est à nullptr que tu ne dois pas veiller à détruire le noeud suivant que s'il existe ;): le test permet de séparer le cas de base (next == nullptr) du cas de récursion

-
Edité par koala01 20 novembre 2017 à 16:41:04

Quand on se retrouve à traiter des arbres de hauteur 1 million,  ou même 100 000, je sais pas, on se pose des questions sur l'adéquation du choix de  la structure de données :-)  Parce que l'arité moyenne des noeuds, elle doit pas être bien grande....