recursivite et profondeur

Version imprimable

bonjour a tous !! j'ai un petit probleme un peu casse tete :

e bosse sur un petit programme dont le coeur est une fonction recursive binaire qui s'arrete quand une precision donnée sur le resultat est atteint.. le probleme c'est que ca peut prendre tres longtemps, je cherche un moyen d'estimer le temps que ca va prendre.

l'idee que j'avais eu, c'etait de regarder le nombre de fois qu'il passait par une certaine profondeur.

par exemple, a priori il va passer en tout 4fois a la profondeur 2, donc la premiere fois j'affiche "0%", la deuxieme foi 25% .. ja 100%.

jusque la tout va bien, sauf que mon programme fonctionne en recursif mais avec une pile que je gere moi meme ( donc en iteratif, en fait :-) ), donc je ne sais pas comment retrouver la profondeur.. voici un pseudo-pseudo-code de mon programme :
Code:

1 2 3 4 5 6 7 8 9 Pile P empiler(element de depart) tant que la pile n'est pas vide A<-- depiler(P) si A verifie une certaine condition, il est stocké (ou viré) sinon, couper A en 2 : A1 et A2 empiler(A1), empiler(A2) fin tant que
voila, en fait j'aimerais savoir s'il y a un moyen de savoir a quelle profondeur on est, en fonction de la taille de la pile et eventuellement de la situation ou on est : est ce qu'on vient de stocker ou de couper, a quelle profondeur on etait la derniere fois..

merci d'avoir tout lu !!

07/07/2006, 23h15
Pragmateek

Passer en paramètre ces données.
08/07/2006, 02h18
LLB

Citation:

Pile P
empiler(element de depart, 1)

tant que la pile n'est pas vide
A, prof <-- depiler(P)
si A verifie une certaine condition, il est stocké (ou viré)
sinon, couper A en 2 : A1 et A2
empiler(A1, prof + 1), empiler(A2, prof + 1)
fin tant que
08/07/2006, 09h30
jobherzt

aaarg, je crois qu'on ne s'est pas compris :-) si c'etait si simple.. mon pseudo code vous a induit en erreur : ma fonction n'est pas "empiler"... "empiler est la fonction standard... qui empile ! le probleme vient justement du fait que j'ai du recursif derecursivé, donc tout est basé sur : tant que la pile n'est pas vide, je mouline. si l'element courant verifie une condition, je le sors, sinon je le coupe et j'empile les 2.. amoins qu'effectivement, je me debrouille pour stocker a cote de chaque element la profondeur a laquelle je l'ai mis.. ca peut se cresuer.

en fait, je pensais plutot a une formule en fonction de la taille de la pile, de l'action effectuée... pour rettrouver la profondeur..

merci, en tout cas !!
11/07/2006, 12h11
LLB

Citation:

Envoyé par jobherzt

amoins qu'effectivement, je me debrouille pour stocker a cote de chaque element la profondeur a laquelle je l'ai mis.. ca peut se cresuer.

Oui, c'est ce que je proposais.
C'est très simple à mettre en oeuvre et relativement efficace.

Citation:

Envoyé par jobherzt

en fait, je pensais plutot a une formule en fonction de la taille de la pile, de l'action effectuée... pour rettrouver la profondeur..

Je ne pense pas qu'on puisse le faire de façon simple. En fonction que l'on se trouve dans le fils gauche ou le fils droit, on n'aura pas la même taille de la pile. Donc, trouver une formule qui marche dans le cas général me semble bien compliqué.
11/07/2006, 12h17
jobherzt

Citation:

Envoyé par LLB

Oui, c'est ce que je proposais.
C'est très simple à mettre en oeuvre et relativement efficace.

oui, du coup j'envisage d'utiliser une deuxieme pile dans laquelle je push/pop les profondeurs associées. je pourrais passer par une structure mais ca m'obligerait a changer pas mal de chose.

Citation:

Envoyé par LLB

Je ne pense pas qu'on puisse le faire de façon simple. En fonction que l'on se trouve dans le fils gauche ou le fils droit, on n'aura pas la même taille de la pile. Donc, trouver une formule qui marche dans le cas général me semble bien compliqué.

c'est bien mon probleme !! j'avis l'intuition qu'il devait y a voir un truc, en fonction de la taille de la pile, de la profondeur calculée precedemment, etc.. mais en fait j'ai l'impression que c'est s'emm... pour rien !

merci a tous, je considere que c'est résolu !