Discussion :

[Tulutu]

Bonjour,

j'essaie un peu la récursivité en C++, je fais une fonction récursive qui calcule la somme des entiers jusqu'à n donné. Elle affiche également "0 + 1 + ... + n = somme", mais alors qu'elle devrait cesser de s'appeler lorsqu'un compteur incrémenté à chaque appel atteint n, hé bien elle continue un peu, allez savoir pourquoi.

Voici le code :

Code c++ :

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
 
void somme_entiers(int n)
{
	static int i = 0;
	static int somme = 0;
 
	if( i < n)
	{
		cout << i << " + ";
		somme += i;
		i++;
		somme_entiers(n);
	}
 
	if( i == n)
	{
		somme += n;
		cout << n << " = " << somme << endl;
	}
}
 
int main()
{
	int n;
 
	if( read_integer(n, 0) ) //fonction perso pour sécuriser la saisie
	{
		cout << "nombre : " << n << endl;
		somme_entiers(n);
	}
 
	return 0;
}

Une idée ?
Merci d'avance.

[ElPedro]

je pense qu'il te manque un "else"

Code :

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

1
2
3
4
5
6
 
	somme_entiers(n);
	}
 
	if( i == n)
	{

Quand tu es arrivé à i == n, et bien tous les appels imbriqués réussissent le test if(i == n). Si tu veux que le code ne passe par i==n qu'1 seule fois, ajoute donc un else entre les 2.

Par ailleurs je n'utiliserai pas "static" ainsi si j'étais toi.
Je te conseille plutôt d'utiliser quelquechose du style :
int somme_entiers(int n, int i, int sommeCourante);

[Tulutu]

Merci, effectivement ça marche avec un else.

Mais je ne comprends pas bien pourquoi ça ne marche pas avec deux if : lorsque le deuxième if est exécuté (et que i == n), tout de suite après la fonction devrait se terminer pour de bon, puisque dans ce deuxième if la fonction ne s'appelle pas elle-même.

Pour les variables "static", pourquoi est-il préférable de les éviter ? techniquement (si on ne prend pas en compte les optimisations du compilateur), cette solution semble plus rapide, puisque la fonction ne copie qu'un seul paramètre au lieu de trois à chaque appel.

[bertry]

Salut,

Mais je ne comprends pas bien pourquoi ça ne marche pas avec deux if : lorsque le deuxième if est exécuté (et que i == n), tout de suite après la fonction devrait se terminer pour de bon, puisque dans ce deuxième if la fonction ne s'appelle pas elle-même.

Parce que ta fonction étant récursive tu reste dans le premier if jusqu’à ce que le test i<n renvoie false quand tu en sors tu as i==n et donc tu exécutes tous les if(i==n) des fonctions appelées précédemment! Alors qu'avec le else tu fais soit if(i<n) soit if(i==n) mais pas les deux dans le même appel de la fonction.

Pour les variables "static", pourquoi est-il préférable de les éviter ? techniquement (si on ne prend pas en compte les optimisations du compilateur), cette solution semble plus rapide, puisque la fonction ne copie qu'un seul paramètre au lieu de trois à chaque appel.

Parce que ça rend ta fonction utilisable pour le calcul d'une seule somme : les membres statiques ne sont initialisés qu'au premier appel de la fonction.
Si tu veux calculer une deuxième somme dans ton main ça donnera n'importe quoi. Suis le conseil avisé de ElPedro

Pour plus de détails : Penser en C++ Chapitre 10.1.1. Variables statiques à l'intérieur des fonctions

[Tulutu]

Tout s'explique, je n'y avais pas pensé, merci pour l'explication et pour le lien.
Pareil pour les variables statiques, effectivement c'est un argument de poids, mais je n'avais testé qu'en faisant un seul appel et du coup ça marchait.

Je mets le sujet en résolu,
À bientôt !

[screetch]

i est initialisée une fois a zéro, même en rappelant la fonction, même recursivement.

[3DArchi]

Salut,
Les variables statiques (locales ou pas), c'est (souvent) mal : source de bug (comme tu en fais l'expérience ), ça fragilise la réentrance, ça cause des cheveux blancs en multithreading, la durée de vie de telles variables est moins évidente (on sait où ça commence, on sait moins bien quand ça fini), et ça rend les fonctions impures, c'est dire si c'est pas bien

techniquement (si on ne prend pas en compte les optimisations du compilateur), cette solution semble plus rapide, puisque la fonction ne copie qu'un seul paramètre au lieu de trois à chaque appel.

techniquement, même sans les optimisations du compilateur, comment peux-tu savoir qu'une variable statique locale prend moins de temps que 3 paramètres ? Peut être qu'elle va être située en mémoire dans une zone couteuse d'accès (plus chère que le passage d'argument) ? Bref, l'idée est d'éviter d'utiliser des features du langage dans des objectifs d'optimisation. « L'optimisation prématurée est la source de tous les maux. », Donald Knuth (citant Dijkstra).


J'ai deux questions :
pourquoi ta fonction ne retourne pas la somme ?
pourquoi ta récursion va de 0 à n et non pas de n à 0 ?

ou dit autrement, si tu construit ta fonction récursive en allant de n à 0 et si la somme est retournée par la fonction, ben plus besoin de variables statiques et un seul paramètre suffit et tout le monde est content


P.S. : 2 remarques complémentaires :
1) si tu as peur de passer trop de paramètres dans ta fonction pour une raison X ou Y, plutôt que d'utiliser des fonctions statiques, utilises une structure de contexte :

Code :

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

1
2
3
4
5
6
7
8
struct somme_contexte
{
int max;
int i_courant;
int somme_courante;
};
 
void somme_entiers(somme_contexte &contexte)

2) alzheimer arrive plus tôt qu'on ne le pense, le temps d'écrire la première remarque, j'en ai oublié la seconde

[koala01]

Salut,

Salut,
Les variables statiques (locales ou pas), c'est (souvent) mal : source de bug (comme tu en fais l'expérience ), ça fragilise la réentrance, ça cause des cheveux blancs en multithreading, la durée de vie de telles variables est moins évidente (on sait où ça commence, on sait moins bien quand ça fini), et ça rend les fonctions impures, c'est dire si c'est pas bien

techniquement, même sans les optimisations du compilateur, comment peux-tu savoir qu'une variable statique locale prend moins de temps que 3 paramètres ? Peut être qu'elle va être située en mémoire dans une zone couteuse d'accès (plus chère que le passage d'argument) ? Bref, l'idée est d'éviter d'utiliser des features du langage dans des objectifs d'optimisation. « L'optimisation prématurée est la source de tous les maux. », Donald Knuth (citant Dijkstra).


J'ai deux questions :
pourquoi ta fonction ne retourne pas la somme ?
pourquoi ta récursion va de 0 à n et non pas de n à 0 ?

ou dit autrement, si tu construit ta fonction récursive en allant de n à 0 et si la somme est retournée par la fonction, ben plus besoin de variables statiques et un seul paramètre suffit et tout le monde est content


P.S. : 2 remarques complémentaires :
1) si tu as peur de passer trop de paramètres dans ta fonction pour une raison X ou Y, plutôt que d'utiliser des fonctions statiques, utilises une structure de contexte :

Code :

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

1
2
3
4
5
6
7
8
struct somme_contexte
{
int max;
int i_courant;
int somme_courante;
};
 
void somme_entiers(somme_contexte &contexte)

2) alzheimer arrive plus tôt qu'on ne le pense, le temps d'écrire la première remarque, j'en ai oublié la seconde

D'autant plus que, pour calculer une somme de manière récursive, un simple

Code :

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

1
2
3
4
5
6
7
8
9
10
11
int sommeRecursive(int valeur)
{
    if(valeur == 0)
    {
        return 0;
    }
    else
    {
        return valeur + sommeRecursive(valeur -1);
    }
}

suffit

Pour la deuxième remarque : ne serait-ce pas

Utiliser une fonction récursive pour calculer une somme, une exponentielle ou une factorielle n'a strictement aucun sens : ce genre de fonction devrait systématiquement être créé sous la forme de boucle, beaucoup plus simple à créer et à comprendre!

Les fonctions récursives ne doivent être envisagée que lorsqu'il s'agit effectivement de la manière la plus simple d'arriver à un résultat (ex : le problème des tours de Hannoï )

[Tulutu]

Merci beaucoup pour vos remarques

Dès que je trouve le temps, je réfléchis à ça plus sérieusement et je vous répond.