Discussion :

[Aleph69]

Parce que, pour toi, près de cent mille appels, ce n'est rien

Non, c'est juste pour montrer le problème du stack overflow.
Ensuite, tu fais réfléchir les étudiants sur une version non récursive et tu leur fais constater que le problème a disparu.

Il est vrai qu'avec les bécanes actuellles, cela semble aller vite, mais, si tu effectuait un certain nobmre de fois le même travail avec une boucle et que tu le chronométrais, puis que tu comparais le temps mis sur le travail basé sur la boucle avec celui basé sur la récursivité, tu verrais une différence assez importante

Oui, je suis bien d'accord avec toi, il est parfait cet exemple de factorielle!

[koala01]

Je ne suis personnellement pas d'accord...

Il est plus facile pour les gens de comprendre qu'il est préférable d'utiliser une boucle chaque fois que possible, et de réserver la récursivité à des cas bien particuliers (quand les boucles sont à la ramasse), que de commencer par leur dire "utilisez la récursivité" et de leur donner la liste des tous les cas où ce n'est décemment pas la meilleure solution.

Apprenons les choses dans l'ordre, si tu veux bien: la règle générale en premier, les exceptions à la règle par la suite, et non le contraire

[Aleph69]

Il est plus facile pour les gens de comprendre qu'il est préférable d'utiliser une boucle chaque fois que possible

Pour le comprendre, il faut en connaître la raison, non?

[bacelar]

La définition de factorielle est récursive, il est donc plus facile de l'aborder ainsi.
Ensuite, il faut montrer qu'une définition mathématique récursive n'implique pas une implémentation informatique récursive.

[Bibibis]

Voilà j'y suis presque, mais j'ai une question:
Comment faire pour demander à l'utilisateur si il veut continuer ou arrêter?
Enfin je vois en gros comment faire. Faire un if avec un break si l'utilisateur répond arrêter et rien s'il répond continuer, mais comment faire pour dire au programme que oui c'est le premier cas et que non c'est le deuxième cas?

[Invité]

Bonjour,
Je voudrais dire un mot à propos des goto.
A l'évidence, c'est la plus grosse faute dans ce code. Mais à mon avis le problème va plus loin.
Que veut dire goto : c'est un branchement (généralement inconditionnel). Le langage prévoit plusieurs syntaxe de boucle (for, do, while). Cela signifie que le bloc d'instructions est exécuté un certain nombre de fois, suivant certaines conditions etc.
Le goto est une instruction de branchement, et en aucun cas une instruction faite pour recommencer un traitement.
Il y a une instruction qui efféctue aussi un branchement : switch, mais il s'agit là du cas typique du branchement conditionnel.

Il y a un cas où l'utilisation du goto est tout à fait correcte et donc justifiée. Soit une fonction longue qui est constitué de petits traitements successifs dépendant d'une condition, par exemple l'instruction lue sur un fichier. Pour la clarté de la démonstration, au début de la fonction des espaces mémoire ou autre sont réservés, fichier ouverts etc., au sortir le la fonction ces réservation doivent être libérées, les fichiers fermés etc..
Or, si un bloc de traitement se passe mal, pour quelque raison que ce soit, naturellement il faut sortir de la fonction, mais il faut libérer les réservations. Le goto permet ce type d'écriture de manière complètement sécurisée. Voici le schéma type :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
int Fonction(...)
{
// séquence de réservation d'espace mémoire ouverture de fichier etc
...
//
  bool fini=false;
  int NumErr=0;
  while (!fini)
  {
// lecture d'un instruction
    string Instruction = Lecture(...);
    if (Instruction == Inst1)
    {
      if (!TraiteInst1(instruction))
      {
          NumErr=1;
          goto FIN;
      }
    }  
    if (Instruction == Inst2)
    {
      if (!TraiteInst2(instruction))
      {
          NumErr=2;
          goto FIN;
      }
    }
//
//    beaucoup de séquences de ce type  
//  
    if (Instruction == Instn)
    {
      if (!TraiteInstn(instruction))
      {
          NumErr=n;  
          goto FIN;
      }
    }  
    if (Instruction == Fini)
    {
      fini = true;  
    }  
  } // fin du while
  int CodeRetour=0; // c'est bon
  FIN:     // il n'y a pas de point-virgule
  if (NumErr != 0)
  {
// on sort en erreur
    CodeRetour = NumErr; 
  }
// Séquence de libération de mémoire, fermeture de fichier etc.
  return CodeRetour;
}

[koala01]

La définition de factorielle est récursive, il est donc plus facile de l'aborder ainsi.
Ensuite, il faut montrer qu'une définition mathématique récursive n'implique pas une implémentation informatique récursive.

La définition "mathématique" d'un carré est bien celle d'un rectangle, et, pourtant, on ne fera jamais hériter une classe carré de la classe rectangle

Plus sérieusement:

Lorsque l'on regarde ce qui doit être fait, c'est:

1. incrémenter un compteur
2. multiplier un résultat par ce compteur
3. comparer la valeur du compteur avec celle de la valeur à atteindre
4. recommencer en 1

C'est ce qui sera fait quelle que soit la manière de s'y prendre, même si la récursive compte en réalité à rebours, mais...

Il faut savoir qu'un appel de fonction (hors cas d' inlining qui n'est de toutes façons pas possible dans le cadre de la récursivité) provoque la mise "sur la pile" d'une série d'informations au moment de l'appel récursif et la récupération de celles-ci au moment où l'on sort de la fonction appelée.

Cela se fait très rapidement, mais, comme ce sont des actions supplémentaires par rapport à l'implémentation itérative, cela augmente le temps d'exécution.

Et, comme ce genre d'actions ne prend pas beaucoup moins de temps que la multiplication, on peut estimer que le rapport de temps est sans doute (je n'ai plus en tête les temps pour les instructions processeurs) de 1 pour 1.5 à 1 pour 2 (avec avantage pour la méthode itérative).

Voilà j'y suis presque, mais j'ai une question:
Comment faire pour demander à l'utilisateur si il veut continuer ou arrêter?
Enfin je vois en gros comment faire. Faire un if avec un break si l'utilisateur répond arrêter et rien s'il répond continuer, mais comment faire pour dire au programme que oui c'est le premier cas et que non c'est le deuxième cas?

En fait, tu dois boucler sur la réponse de l'utilisateur.

Tu ne dois pas utiliser un if, et encore moins un break (il est conseillé de les réserver au switch...case), mais plutôt "boucler" "jusqu'à" ce que le choix de l'utilisateur indique qu'il souhaite arrêter

[koala01]

Bonjour,
Je voudrais dire un mot à propos des goto.
A l'évidence, c'est la plus grosse faute dans ce code. Mais à mon avis le problème va plus loin.
Que veut dire goto : c'est un branchement (généralement inconditionnel). Le langage prévoit plusieurs syntaxe de boucle (for, do, while). Cela signifie que le bloc d'instructions est exécuté un certain nombre de fois, suivant certaines conditions etc.
Le goto est une instruction de branchement, et en aucun cas une instruction faite pour recommencer un traitement.
Il y a une instruction qui efféctue aussi un branchement : switch, mais il s'agit là du cas typique du branchement conditionnel.

Il y a un cas où l'utilisation du goto est tout à fait correcte et donc justifiée. Soit une fonction longue qui est constitué de petits traitements successifs dépendant d'une condition, par exemple l'instruction lue sur un fichier. Pour la clarté de la démonstration, au début de la fonction des espaces mémoire ou autre sont réservés, fichier ouverts etc., au sortir le la fonction ces réservation doivent être libérées, les fichiers fermés etc..
Or, si un bloc de traitement se passe mal, pour quelque raison que ce soit, naturellement il faut sortir de la fonction, mais il faut libérer les réservations. Le goto permet ce type d'écriture de manière complètement sécurisée. Voici le schéma type :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
int Fonction(...)
{
// séquence de réservation d'espace mémoire ouverture de fichier etc
...
//
  bool fini=false;
  int NumErr=0;
  while (!fini)
  {
// lecture d'un instruction
    string Instruction = Lecture(...);
    if (Instruction == Inst1)
    {
      if (!TraiteInst1(instruction))
      {
          NumErr=1;
          goto FIN;
      }
    }  
    if (Instruction == Inst2)
    {
      if (!TraiteInst2(instruction))
      {
          NumErr=2;
          goto FIN;
      }
    }
//
//    beaucoup de séquences de ce type  
//  
    if (Instruction == Instn)
    {
      if (!TraiteInstn(instruction))
      {
          NumErr=n;  
          goto FIN;
      }
    }  
    if (Instruction == Fini)
    {
      fini = true;  
    }  
  } // fin du while
  int CodeRetour=0; // c'est bon
  FIN:     // il n'y a pas de point-virgule
  if (NumErr != 0)
  {
// on sort en erreur
    CodeRetour = NumErr; 
  }
// Séquence de libération de mémoire, fermeture de fichier etc.
  return CodeRetour;
}

Et encore...

C'est *éventuellement* vrai dans les langages qui ne fournissent pas le support du RAII et / ou les exceptions, mais il faut avouer que, en C++, on dispose de tellement de possibilités (exceptions et programmation structurée en tête) de l'éviter que l'utilisation de goto est généralement le signe que l'on n'a pas pris le temps de réfléchir suffisamment à ce que l'on doit faire

[Bibibis]

D'accord, j'avais pensé à cette solution, mais comment faire pour que si l'utilisateur marque oui, ça transforme ma valeur boléene en true et si il marque non, ça transforme ma valeur boléene en false?

C'est la seule place ou je coince, sinon voilà le code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// Factorielle.cpp*: définit le point d'entrée pour l'application console.
//
 
#include <StdAfx.h>
#include <iostream>
 
 
int main(void)
{
	std::cout << "Calcul de la factorielle" << std::endl;
	unsigned int x, n;
	long double y;
	bool r;
	while (r=true)
	{
		y=1;
		do
		{
			x=0;
			std::cout << "Entrez un nombre entre 0 et 30 : ";
			std::cin >> x;
		} while (x<0, x>30);
		n=x;
		for (;x>1;x--)
		{
			y=x*y;
		}
		std::cout << "La factorielle de " << n << " est " << y << std::endl << "Continuer? ";
		std::cin >> r;
	}
	return 0;
}

[koala01]

Sais tu que tu peux comparer des chaines de caractères entre elles, surtout si tu les manipules avec la classe fournie par le standard fournie à cet effet (la classe string, disponible dans l'espace de noms std par simple inclusion du fichier d'en-tête <string>)

Tu peux donc parfaitement comparer une chaine de caractères sous une forme proche de reponse == "oui" (ou reponse == "non", selon test besoins).

Idéalement, tu devrais veiller au moins à supporter les différentes casses, mais ce n'est pas le problème principal

[Bibibis]

Voilà, je crois que j'y suis, en tout cas j'ai essayé le programme sous tous les aspects possibles et ça marche. Si il y a encore des erreurs dites moi. Sinon je vais l'imprimer pour le rendre demain.

Edit: J'ai enlevé l'entête précompilé.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <string>
 
int main(void)
{
	std::cout << "Calcul de la factorielle" << std::endl;
	unsigned int x, n;
	long double y;
	std::string reponse;
	reponse="oui";
	while (reponse == "oui")
	{
		y=1;
		do
		{
			x=0;
			std::cout << "Entrez un nombre entre 0 et 30 : ";
			std::cin >> x;
		} while (x<0, x>30);
		n=x;
		for (;x>1;x--)
		{
			y=x*y;
		}
		std::cout << "La factorielle de " << n << " est " << y << std::endl << "Continuer? oui/non : ";
		std::cin >> reponse;
	}
	return 0;
}

[Invité]

S'il vous plait Koala, laissez un débutant découvrir la logique avant de lui enseigner l'art d'appliquer les finesses et les possibilités d'un langage.

Concernant mon post sur le goto, je sais bien (naturellement) que ce n'est pas la seule solution, mais il se trouve que le goto fait partie du langage, pendant des années, je l'ai ignoré, cad que je me le suis interdit, puis je l'ai appliqué à des cas très limités, tel que je l'ai décrit.
Par ailleurs, j'ai lu quelque-part que le source de Linux en était plein.

[koala01]

S'il vous plait Koala, laissez un débutant découvrir la logique avant de lui enseigner l'art d'appliquer les finesses et les possibilités d'un langage.

Concernant mon post sur le goto, je sais bien (naturellement) que ce n'est pas la seule solution, mais il se trouve que le goto fait partie du langage, pendant des années, je l'ai ignoré, cad que je me le suis interdit, puis je l'ai appliqué à des cas très limités, tel que je l'ai décrit.
Par ailleurs, j'ai lu quelque-part que le source de Linux en était plein.

Le fait est que, justement, la logique nous permet très souvent d'éviter le recours au goto, quel que soit le langage envisagé.

Pour autant que je m'en souvienne, je n'ai jamais été, quel que soit le langage utilisé, confronté à une situation dans laquelle je n'avais pas d'autre choix que d'utiliser le goto

Je sais bien qu'on en trouve énormément dans le noyau linux, mais nous sommes justement dans cette catégorie de cas particuliers.

Et, justement, face à un débutant, il est largement préférable de dire "le goto est bon pour la poubelle", quitte à ce qu'il se rende compte par la suite qu'il peut effectivement s'avérer utile dans des cas très particulier, plutôt que de faire comme s'il était tout à fait normal de l'utiliser.

C'est d'autant plus vrai lorsque l'on vient à parler d'un langage qui fournit certains mécanismes, entre autre quant à la destruction automatique des variables, comme C++.

[Bibibis]

Mais c'est quoi le problème du goto au fait? Il ralentit le langage?

[Joel F]

S'il vous plait Koala, laissez un débutant découvrir la logique avant de lui enseigner l'art d'appliquer les finesses et les possibilités d'un langage.

Concernant mon post sur le goto, je sais bien (naturellement) que ce n'est pas la seule solution, mais il se trouve que le goto fait partie du langage, pendant des années, je l'ai ignoré, cad que je me le suis interdit, puis je l'ai appliqué à des cas très limités, tel que je l'ai décrit.
Par ailleurs, j'ai lu quelque-part que le source de Linux en était plein.

clair que le code Linux c'est la référence :€
le code spagetthi moins on en mange, mieux on se porte.

Donc en C++, RAII+exception.

[Joel F]

Tiens, il faudra que j'essaie!
Ma dernière expérience remonte à Visual 6 et il ne le faisait pas pour DFS.
A moins qu'il faille spécifier une option supplémentaire par rapport aux classiques O2 & Cie?

MSVC 2008 et gcc > 3.4 le font en -O3

[bacelar]

koala01, si je fais une bibliothèque contenant des objets géométriques au sens mathématique, Carré dérivera de Rectangle, quitte à mettre des accesseurs et des mutateurs sur width et length.
L'usage, donc le système de pensée de l'utilisateur prime sur l'élégance de l'implémentation.

Un usage élégant donne un code maintenable, pas un code concis et cryptique.

Rien d’interdit d’apprendre à linéariser une récursion finale, mais il faut déjà comprendre la récursion et ce n’est qu’une optimisation. Comme toute les optimisations, elle n’est pas forcement efficace partout et elle doit être menée qu’à partir d’un code (ou d’un algo quand on n’est plus aguerri) qui est déjà correcte.

[koala01]

Mais c'est quoi le problème du goto au fait? Il ralentit le langage?

Non, il ne ralentit pas vraiment le langage...

Ce qui se passe essentiellement, c'est qu'il a la sale manie de transformer le code en "code spagetti": on fini très rapidement par perdre le fil de la logique, à force de sauter d'une ligne à l'autre.

koala01, si je fais une bibliothèque contenant des objets géométriques au sens mathématique, Carré dérivera de Rectangle, quitte à mettre des accesseurs et des mutateurs sur width et length.
L'usage, donc le système de pensée de l'utilisateur prime sur l'élégance de l'implémentation.

Et pourtant...

Si tu travailles avec un carré, tu utilisera des caractéristiques propres qui font que tu ne t'inquiète pas de l'angle que peuvent faire les diagonales, ni de la différence de taille qui peut exister entre deux cotés, ni...

S'il est logique que tu demande la longueur et la largeur pour un rectangle, cela n'aura en retour aucun sens pour un carré, et cela devient dangereux pour l'utilisateur car tu lui laisse le choix de décider d'utiliser l'un ou l'autre, avec le risque de confusion qui s'en suit (car les deux dimensions sont strictement identiques )

Un usage élégant donne un code maintenable, pas un code concis et cryptique.

Un usage élégant te fournira un code compréhensible, maintenable et... "aussi conçis que faire se peut", sans pour autant être cryptique

Et, pour en revenir à l'intérêt de la boucle par rapport à celui de la récursivité, je trouve, à titre personnel que la boucle est autrement plus compréhensible et maintenable que la récursivité

Rien d’interdit d’apprendre à linéariser une récursion finale, mais il faut déjà comprendre la récursion et ce n’est qu’une optimisation. Comme toute les optimisations, elle n’est pas forcement efficace partout et elle doit être menée qu’à partir d’un code (ou d’un algo quand on n’est plus aguerri) qui est déjà correcte.

Le problème, vois tu, c'est que, lorsque tu pars du code, tu vas plus t'intéresser aux "sucres syntaxiques" autorisés par le langage qu'à l'algorithme, dans l'espoir d'améliorer les performances.

Or, les plus gros gains que l'on observe sont ceux qui traitent directement l'algorithme.

Une optimisation de l'algorithme, si elle permet de ne pas passer par un bloc d'instructions quand ce n'est pas nécessaire, sera toujours beaucoup plus intéressante que le fait de gagner quelques cycles processeurs grâce à un sucre syntaxique, surtout si le bloc d'instructions est important et que l'on évite un grand nombre de passages

[Invité]

Mais c'est quoi le problème du goto au fait? Il ralentit le langage?

Le goto est fait pour un branchement inconditionnel. Cela sous-entent, "je m'en vais là-bas parce que je n'ai plus rien à faire ici."
Vous pouvez aller faire votre marché avec des échasses, mais c'est pas vraiment pratique.
Les compilateurs (le mien en tout cas) vérifie qu'il n'y a aucune déclaration dans le bloc sauté pas le goto. Autrement dit ce bloc goto est un bloc à par entière avec ses obligations propres.
La notion de boucle est importante à comprendre. Cela veut dire "faire un certain nombre de fois (presque) la même chose, jusqu'à ce qu'une certaine condition soit remplie".

A propos de la récursivité, en Fortran ce n'était pas autorisé, donc on trouvait une astuce pour "tromper" le compilateur.
Quand j'ai commencé avec le C, au chapitre de la récursivité le contre-exemple du calcul de la factorielle était expliqué (à cette époque, l'inconvénient était le temps d'exécution). On ne peut pas remettre en cause la compétence des auteurs de ce livre, mais il exigeait un pré-requis minimum, aussi bien en mathématiques qu'en logique.

[koala01]

Attention, je ne remet pas (forcément) la compétence des auteurs de cours et de tutos en cause, bien que je pourrais sans doute le faire pour certains...

Ce que je remet en cause, c'est le choix malheureux de la factorielle comme exemple destiné à introduire la récursivité.
Cela me donne l'occasion de mieux répondre à bacelar concernan

Un usage élégant donne un code maintenable, pas un code concis et cryptique.

Le problème que pierre explique avec fortran est bel et bien la preuve de ce que j'avance: la récursivité, tout utile qu'elle puisse être (et dieu sait que je l'apprécie énormément) n'est "qu'une possibilité parmi d'autres" qui vaut la peine d'être envisagée.

Encore faut il déjà qu'elle soit autorisée par le langage mais, une fois autorisée, elle ne doit être envisager que lorsqu'il n'y a pas d'autre solution élégante ou que les autres solutions s'avèrent, définitivement, inefficaces.

L'usage élégant est l'usage du code *le plus simple possible* susceptible de faire ce que l'on attend de lui.

Une boucle quelle qu'elle soit est une solution particulièrement simple, dont le principe est appris dés les débuts en programmation.

Tant que leur utilisation ne nous force pas à trouver des solutions abracadabrantesques pour les utiliser, elles devraient donc être préférées à toute autre solution plus complexe.

La récursivité est une technique des plus intéressante, mais également une technique déjà plus complexe à mettre en oeuvre qu'une simple boucle (cf les raisons que j'ai donné plus tôt concernant sa mauvaise réputation ).

C'est loin d'être une mauvaise technique, mais c'est une technique à utiliser "en dernier recours", lorsque l'on n'a décidément "pas d'autre option efficace" (un peu à l'instar du goto, finalement ).

Décider de recourir à la récursivité pour résoudre un problème tel que la factorielle d'un nombre revient, en définitive, à utiliser un bazooka contre un moustique.

Maintenant, il est clair qu'il ne faut pas tomber dans l'excès inverse qui consiste à refuser toute idée de récursivité, à moins d'y être obligé par le langage (ce qui n'est pas le cas de C et de C++).

Tenter, par exemple, de parcourir un arbre ou de résoudre le problème des tours de Hannoï sans recourir à la récursivité est tout à fait possible, mais beaucoup moins facile et évident à mettre en oeuvre.

Nous entrons donc parfaitement dans ce cadre de cette condition de "pas d'autre option efficace" et de "dernier recours" que je viens de citer

De là à utiliser la factorielle pour introduire la récursivité, il faut comprendre que, si tu présente ce problème à quelqu'un qui connait les boucles et à qui tu n'a pas encore fait remarquer qu'une fonction pouvait parfaitement s'appeler elle-même, il ne pensera jamais à recourir à la récursivité, et travaillera avec des boucles