Discussion :

[mielle]

Bonjour,
Je veux simplement qu'elle est la méthode souffrent de coût de calcul élevé
est ce que les méthodes itératives ou celle récursives

[ternel]

Ca ne veut rien dire.
Il n'y a pas de question dans ce que tu dis.

Par contre, en général, la récursion est plus coûteuse. En temps à cause des appels de fonctions successifs.
Par contre, l'itération aura souvent besoin de plus de mémoire.
La récursion est plus lente à cause des multiples appels de fonction.
L'itération est plus rapide, mais peut requérir plus de mémoire allouée en même temps.


Il s'agit souvent d'un compromis, et souvent, les gens se tournent vers l'itération.

[mielle]

Par contre, en général, la récursion est plus coûteuse. En temps à cause des appels de fonctions successifs.

En effet ,vous avez répondus à ma question

[Neckara]

Bonjour,

L'itération est plus rapide, mais peut requérir plus de mémoire allouée en même temps.

Il faut différencier deux choses : l'algorithme et l'implémentation.

Niveau algorithme, entre l'itératif et le récursif, je ne vois pas vraiment de raison pour que l'itératif prenne plus de mémoire que le récursif.
Par contre je ne suis pas sûr qu'on puisse toujours convertir un algorithme récursif en un algorithme itératif.

Au niveau de l'implémentation, on peut implémenter n'importe quel algorithme récursif en itératif en recréant une pile. Dans ce cas là l'implémentation itérative coûtera toujours moins de mémoire que la récursive.
Après selon l'implémentation on utilisera plus ou moins de mémoire.

Mais je pense que la vitesse ou la mémoire utilisées restent vraiment des critères secondaires.

Je pense que la principale chose à regarder est avant tout la lisibilité du code.
Après il me semble avoir lu que la récursivité pouvait être dangereuse si on l'utilise pour gérée les E/S :

Code :

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

1
2
3
4
5
6
7
8
int foo(void)
{
       int i;
       std::cin >> i;
       if( i > 10)
             return foo();
       return i;
}

Car l'utilisateur pourrait s'amuser à ne donner que des réponses fausses et exploser la pile, après je ne connais pas les détails mais il serait possible à partir de là d'exploiter cette faille (?).

[Iradrille]

Mais je pense que la vitesse ou la mémoire utilisées restent vraiment des critères secondaires.

Je pense que la principale chose à regarder est avant tout la lisibilité du code.
Après il me semble avoir lu que la récursivité pouvait être dangereuse si on l'utilise pour gérée les E/S :

Code :

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

1
2
3
4
5
6
7
8
int foo(void)
{
       int i;
       std::cin >> i;
       if( i > 10)
             return foo();
       return i;
}

Car l'utilisateur pourrait s'amuser à ne donner que des réponses fausses et exploser la pile, après je ne connais pas les détails mais il serait possible à partir de là d'exploiter cette faille (?).

Tout dépend du contexte, si on travaille sur du temps réel, la vitesse compte bien plus que la lisibilité du code.

Sinon pour l'exploit, je pense pas que ce soit possible

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void foo() {
	int i=42;
	for(int j=0; j<42; ++j) {
		i += j;
	}
} // juste avoir du code à remplacer
 
int main() {
 
	auto pfoo = &foo;
	*((unsigned char*)pfoo) = 0xc3; // ret
 
	return 0;
}

Violation d'accès, par défaut on à pas les droits d'écriture sur les segments de code, dans le pire des cas on peut peut être pourrir d'autres variables, mais rien de méchant je pense.

[Neckara]

Tout dépend du contexte, si on travaille sur du temps réel, la vitesse compte bien plus que la lisibilité du code.

Il est vrai que lorsqu'on code dans l'espace noyau ou en temps réel la lisibilité est souvent laissée en second plan, mais ce sont des cas assez spécifiques.

Sinon pour l'exploit, je pense pas que ce soit possible

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void foo() {
	int i=42;
	for(int j=0; j<42; ++j) {
		i += j;
	}
} // juste avoir du code à remplacer
 
int main() {
 
	auto pfoo = &foo;
	*((unsigned char*)pfoo) = 0xc3; // ret
 
	return 0;
}

Violation d'accès, par défaut on à pas les droits d'écriture sur les segments de code, dans le pire des cas on peut peut être pourrir d'autres variables, mais rien de méchant je pense.

Heureusement qu'on a pas les droits d'écritures sur les segments de code mais pourrir des variables est loin d'être "rien de méchant" au contraire surtout dans le cas de serveurs

Je pense que cette faille était surtout utilisée quand on avait dans la mémoire la pile "en bas" et le tas "en haut"
La pile "montait" au fur et à mesure qu'elle grandissait et le tas "descendait".
Il arrivait donc que la pile "rencontre" le tas. On pouvait alors réécrire dans le tas avec la pile parfois sans générer d'erreurs.

[Flob90]

Iteratif / recursif c'est une notion d'algorithme, pas d'implementation. Et de mémoire, il doit y avoir une preuve de l'existance d'un algo recursif quand on a un iteratif et vice et verse (recursif terminal en plus je crois). Le problème étant de trouver les équivalents (ca marche aussi dans l'autre sens). L'equivalence est en temps. En mémoire, je doute de la preuve pour l'equivalence d'un recursif terminal.

Après il faut bien être conscient que les structures de données employé (ie de manière formelle) incite à penser d'un façon ou d'un autre.

Quand à la différence de performance, j'attend toujours de voir un benchmark pertinant sur le sujet (iteratif,recursif et recursif terminal, avec et sans effet de bord, en optimisé). En attendant, j'ai tendance à penser que si j'ai un algo recursif terminal sans effet de bord, le compilateur est bien assez intelligent pour optimiser et obtenir les mêmes performances en temps qu'en iteratif.

Pour ce qui est de la mémoire, la question ne se pose même pas, écrire (de manière formelle) les deux algos donne instantanément la réponse sur la différence pour la mémoire. La question se pose uniquement pour le temps car la compilation naïve d'un algo recursif passe par une pile coûteuse, sauf que les compilateur optimise de manière intelligente.

[Médinoc]

^^Enfin, sur un système genre PC, le débordement de pile cause plus souvent une Denial of Service qu'une vraie corruption, parce qu'entre la pile et le tas il y a au moins une page sur laquelle on n'a pas les droits.

Sous Windows (où il me semble que c'est explicitement spécifié, d'ailleurs), cela se traduit par une exception Win32 STATUS_STACK_OVERFLOW. Le symptôme visible est (était?) que le programme crashe immédiatement sans boîte de dialogue de rapport d'erreurs, car il n'y a même plus assez de pile pour lancer le programme approprié.

[LinuxUser]

Tu parles de coût mémoire ou de temps de calcul?

De manière générale, vaux mieux éviter la récursion, après il y a toujours des cas particuliers.

[ternel]

Tu parles de coût mémoire ou de temps de calcul?

C'était mal dis, je l'ai rectifié.