récursivité et itérativité

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

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.

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.

Citation:

---

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

Citation:

---

Envoyé par LinuxUser

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

---

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

Bonjour,

Citation:

---

Envoyé par leternel

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:

---

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 (?).

Citation:

---

Envoyé par Neckara

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:

---

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:

---

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.

Citation:

---

Envoyé par Iradrille

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.

Citation:

---

Envoyé par Iradrille

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

Code:

---

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 :aie: mais pourrir des variables est loin d'être "rien de méchant" au contraire surtout dans le cas de serveurs :aie:

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.

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.

^^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é.

Salut,

De manière générale, j'aurais tendance à conseiller de travailler de manière itérative, sauf si l'algorithme récursif permet de travailler réellement de manière plus simple (ou si l'on veut travailler en programmation générique).

Ainsi, il n'y a pas vraiment de raison (autre que la figure de style :D) d'implémenter une factorielle ou une exponentielle de manière récursive: une simple boucle suffit amplement et n'est pas plus compliquée (au contraire!) que l'algorithme récursif à utiliser.

Par contre, si tu veux implémenter un algorithme de résolution des tours de hannoï, par exemple, tu vas avoir énormément de mal à l'implémenter de manière itérative. L'algorithme récursif est alors la moins mauvaise solution, car c'est réellement la solution la plus facile.

De même, si tu envisages d'implémenter une factorielle ou une exponentielle sous la forme de template (après tout, pourquoi pas :question:) la récursivité sera ton amie car cela permettra de fournir directement la valeur exacte calculée au moment de la compilation, plutot que de provoquer le calcul à l'exécution.

Mais les cas dans lesquels une factorielle ou une exponentielle template s'avère utile sont malgré tout relativement rares ;)

Apres les bons compilos derecursifie pas mal d'algo recursif de leur propre chef.