Discussion :

[zenux]

Bonjour,

J'ai souvent entendu dire que l'ont pouvait éviter la récursivité et donc je me demandait si c'était possible de l'éviter pour ça:

Comment faire une fonction non récursive qui listerait un répertoire et ainsi que ses sous-répertoires pour les afficher sous forme d'un arbre ? Est-ce possible ?

Merci...

[Hephaistos007]

Les algorithmes récursifs peuvent être transformés en leur équivalent en itératifs (mais pas tous). Tout simplement parce que la récursivité c'est un empilement de valeurs à chaque appel, effectué automatiquement à l'éxécution. A partir de là, il suffit de reproduire ce principe à l'aide d'une structure de donnée FIFO (Pile).

Cherche du coté de la derecursification sous google.

[zenux]

Merci mais je demandait si il y avait moyen de supprimer la récursivité pour avoir plus de performance et donc immité la récurivité ne m'interresse pas

[ToTo13]

Bonjour,

tu peux lister tres facilement les dossiers, sous répertoires et fichiers sans faire de récursivité.
Mais pour ce qui est de créer un arbre sans utiliser de récursivité, là j'ai un doute.

Est ce que tu souhaites éviter la récursivité parce que c'est imposé dans ton exo (ou autre) ou est ce tout simplement parce que tu n'aimes pas les récursivités ???

[Hephaistos007]

Merci mais je demandait si il y avait moyen de supprimer la récursivité pour avoir plus de performance et donc immité la récurivité ne m'interresse pas

Justement, on transforme les algos récursifs en itératifs pour les optimiser puisque qu'un traitement itératif est toujours plus performant.


Pour en revenir à ton histoire de repertoires, ils sont organisés sous forme d'un arbre (on parle bien de l'arborescence des répertoire).
Il existe 2 parcours d'arbre :
- En profondeur : nécessite le concept de récursivité et peut être "émulé" en itératif comme je te l'ai dit
- En largeur : ne nécessite pas de récursivité. C'est un algo itératif de traitement d'une liste (LIFO).

Conclusion : la solution la plus simple est le parcours en largeur de tes répertoires.

[ToTo13]

euh...

Iteratifs vs recursif est toujours soumi à débat !!

[pcaboche]

Conclusion : la solution la plus simple est le parcours en largeur de tes répertoires.

Pas forcément, si on veut faire un équivalent de la commande "tree", il faut faire un parcours en profondeur. Reste à savoir si la méthode de parcours a de l'importance ou si les répertoires peuvent être traités dans un ordre queconque.

Ce qui est couteux dans la méthode récursive, ce sont les appels répétés de fonctions (allocations des variables et paramètres dans la pile) qu'on peut effectivement remplacer par une pile.

Notez au passage qu'avec les langages fonctionnels (style Ocaml) on programme tout de manière récursive et c'est le compilateur qui fait le travail de "dérécursification".

[HanLee]

puisque qu'un traitement itératif est toujours plus performant.

Ca c'est pas vrai.

[Hephaistos007]

puisque qu'un traitement itératif est toujours plus performant.

Ca c'est pas vrai.

Et l'argumentation ? tu en dis trop ou pas assez.

[HanLee]

puisque qu'un traitement itératif est toujours plus performant.

Ca c'est pas vrai.

Et l'argumentation ? tu en dis trop ou pas assez.

Ben quand tu te mets en récursivité terminale, ton code reste simple et lisible à comprendre, proche de l'algorithme, et avec une vitesse égale à une version itérative, plus lourde et moche. (le compilateur va transformer ton appel de fonction différemment de façon à ne pas faire déborder la pile).

OCaml sait faire ça comme disait très bien pcaboche, mais les compilateurs assez récents C/C++ font ça très bien aussi.

Beaucoup de gens ne connaissent pas cette fonctionnalité, et passent à coté de la puissance (concision, expressivité) de la récursivité à cause de ça. Surtout ceux qui ont toujours pratiqué des langages principalement itératifs (C, C++, Pascal).

[Hephaistos007]

Ben quand tu te mets en récursivité terminale, ton code reste simple et lisible à comprendre, proche de l'algorithme, et avec une vitesse égale à une version itérative, plus lourde et moche.

Le récursivité terminale n'est qu'une condition à sa transformation en itérative. Ce n'est donc pas le débat. Moi je suis juste intrigué par ton affirmation "avec une vitesse égale à une version itérative". D'où sort cela, tu as fais des tests ? tu as des références bibliographiques ?

Pour pouvoir comparer, il faut un algo en récursif et son équivalent en itératif. A partir de là, il est intuitif de penser qu'empiler des contextes c'est moins optimisé qu'empiler uniquement les valeurs utiles à ton algo

Beaucoup de gens ne connaissent pas cette fonctionnalité, et passent à coté de la puissance (concision, expressivité) de la récursivité à cause de ça. Surtout ceux qui ont toujours pratiqué des langages principalement itératifs (C, C++, Pascal).

Moi je ne suis pas de ces gens là, je fais du récursif partout où je peux.

[PRomu@ld]

puisque qu'un traitement itératif est toujours plus performant.

Jamais démontré non plus ...(algorithmiquement parlant) . Et puis pour ce qui est des appels de fonction qui coutent, elle compense en fait l'utilisation de la pile pour la dérécursification.

Quand bien même il y aurait une différence de performance, où se situe t'elle ? Si ça se joue à quelques cycles d'horloge, on en conviendra, ça ne sert strictement à rien !

Le seul fait qui me fait quelque fois choisir l'itératif par rapport au récursif c'est que quelque fois on fasse débordé la pile des appels ... mais ceci est un problème pratique.

[fearyourself]

puisque qu'un traitement itératif est toujours plus performant.

Jamais démontré non plus ...(algorithmiquement parlant) . Et puis pour ce qui est des appels de fonction qui coutent, elle compense en fait l'utilisation de la pile pour la dérécursification.

Quand bien même il y aurait une différence de performance, où se situe t'elle ? Si ça se joue à quelques cycles d'horloge, on en conviendra, ça ne sert strictement à rien !

Le seul fait qui me fait quelque fois choisir l'itératif par rapport au récursif c'est que quelque fois on fasse débordé la pile des appels ... mais ceci est un problème pratique.

La conclusion de l'histiore est de ne jamais utiliser le mot jamais et toujours éviter le mot toujours lorsqu'on compare la méthode récursive et la méthode itérative.


Jc

[Hephaistos007]

La conclusion de l'histiore est de ne jamais utiliser le mot jamais et toujours éviter le mot toujours lorsqu'on compare la méthode récursive et la méthode itérative.

Jc

Oui tu as raison. J'ai toujours su au fond de moi qu'on aurait jamais du aborder ce sujet.
A+

[Caine]

Un algorithme récursif est plus performant qu'un itératif et vice-versa?

La réponse dépend de la traduction en assembleur. Elle dépend notamment :
1 - du nombre d'argument à empiler pour l'algo récursif.
2 - du nombre de variables en mémoire à manipuler pour l'aglo itératif
3 - de la complexité de chaque algorithme.

Pour 1 -
Soit un algorithme récursif est mal implémenté. Il a une meilleure complexité que l'itératif.
Mais, la taille des arguments passés est importante : les performances seront fortement dégradées en raison de l'empilement sur le tas des arguments. Il peut même aboutir à un plantage par débordement de pile.

Un algorithme itératif, manipulant peu ou mieux les variables en mémoire, même avec une complexité supérieure sera plus performant.

Pour 2-
Soit un algorithme itératif très complexe, mais ayant une complexité inférieure à l'équivalent récursif. Disons qu'il manipule pour son déroulement un grand nombre de variables... globales et nécessite des sauts large en pointeur...il est moins performant qu'un algo récursif qui manipulera des arguments sur le tas.

[HanLee]

Le récursivité terminale n'est qu'une condition à sa transformation en itérative. Ce n'est donc pas le débat. Moi je suis juste intrigué par ton affirmation "avec une vitesse égale à une version itérative". D'où sort cela, tu as fais des tests ? tu as des références bibliographiques ?

Pour pouvoir comparer, il faut un algo en récursif et son équivalent en itératif. A partir de là, il est intuitif de penser qu'empiler des contextes c'est moins optimisé qu'empiler uniquement les valeurs utiles à ton algo

Pour le "égal" faut pas prendre tout à la lettre non plus. J'ai pas de chiffres, mais des explications que j'ai lues et trouvées sur Google, dans la documentation de OCaml, dans le site des Universités, Polytechnique, ENS, et tout ça.

Mais moi je pense que c'est rigoureusement égal ! Si la fonction est dérécursifiée par le compilateur, il n'y a plus d'empilements des paramètres dans la pile, donc il n'y a plus d'appels répétés à la fonction, c'est remplacé par un truc du genre goto. C'est un for/while déguisé.

Où est la magie alors ? Ben c'est que souvent pour mettre un algo sous forme récursive terminale, tu utilises un accumulateur, qui sert de compteur, variable de stockage, exactement ce que t'aurais utilisé pour la version itérative.

Exemple en C++ :

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
 
int factorielle(int n, int accu)
{
    if (n < 2) { return accu; }
    else { return factorielle(n-1, n*accu) }
}
 
// Code équivalent
int factorielle_bis(int n)
{
    int res = 1;
    for (int i = n; i >= 2; --i)
        res = res * i;
    return res;
}
 
// La version que normalement on écrirait, c'est la même mais dans l'autre sens
int factorielle_bisbis(int n)
{
    int res = 1;
    for (int i = 2; i < n; ++i)
        res = res * i;
    return res;
}

Bon, ça nécessite un paramètre en plus, mais normalement si on pouvait avoir des nested functions, l'utilisation ne changerait pas (on utiliserait une une fonction auxiliaire cachée).
Le n * accu c'est res = res * i
Le test i >= 2 c'est le contraire de i < 2
return accu c'est return res

Voilà! C'est la même non ?

Beaucoup de gens ne connaissent pas cette fonctionnalité, et passent à coté de la puissance (concision, expressivité) de la récursivité à cause de ça. Surtout ceux qui ont toujours pratiqué des langages principalement itératifs (C, C++, Pascal).

Moi je ne suis pas de ces gens là, je fais du récursif partout où je peux.

C'est cool alors