bonjour a tous !
j'ai un probleme disons plutot theorique...

je 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, donc je ne sais pas comment retrouver la profondeur.. voici un pseudo-pseudo-code de mon programme :
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 !!

L'idéal est de passer la profondeur en paramètre facultatif :

function recursive(..., $profondeur = 0) {
    ...
    recursive(..., $profondeur+1);
    ...
}

Ainsi dans la fonction, le paramètre $profondeur est la profondeur de l'appel, tout simplement

Pour le nombre de passages, on utilisera une variable globale, ou mieux, statique :

function recursive(..., $profondeur = 0) {
    static $passages = array();
    $passages[$profondeur] = isset($passages[$profondeur]) ? $passages[$profondeur]+1 : 1;
     ...
     recursive(..., $profondeur+1);
     ...
} 

Ainsi dans ta fonction tu as une variable sous forme de tableau tel que $passages[$i] = "nombre de passages à la profondeur $i".

Selon les possibilités du langage (je te l'ai mis en php pour que tu situes bien), l'argument "profondeur" sera ou non facultatif (sinon il nécessitera de le définir à 0 au premier appel), la variable "passages" sera statique ou globale, mais dans tous les cas le tableau fonctionnera puisqu'il s'agit d'un tableau indexé sur des entiers, et qui sera bien sûr rempli dans l'ordre (impossible de passer de profondeur 3 à 5 sinon c'est qu'il y a un problème donc si on définit $passages[$n+1] c'est que $passages[$n] est définie).

Pareil pour l'état : une fonction $etat statique (idéalement) ou globale que tu définis juste avant d'appeler "stocker()" ou "couper()".

Le principe mis à l'épreuve:

Surtout pas des ++ mais +1
Sinon la profondeur ne redescend jamais : les deux appels successifs sont bien à la même profondeur.

je viens de me rendre compte que mon pseudo code n'etait pas si clair... si c'etait si simple

helas, le probleme est que je n'ai pas une vraie fonction recursive, plutot du recursif derecursivé.. donc empiler n'est pas le nom de mafonction, mais une fonction... de la pile !

donc je n'ai pas d'appel recursif, mais un "tant que".. en gros, je gere la pile "manuellement". donc je ne peux pas passer de profondeur en parametre. j'essaie donc de deuire la profondeur ( ce qui correspondrait a la profondeur si jetais en recursif) a partir de la taille de la pile et autres parametres !

en gros : si l'element courant verifie une certaine condition, je le sors, sinon je le coupe en 2 et j'empile chacune des moities. et je m'arrete quand la pile est vide.

Le principe reste le même, tu as une variable $profondeur, que tu fixes à 0 avant de rentrer dans ta boucle, et que tu incrémentes/décrémentes dans les différentes parties de ta boucle. Il ne faut pas déduire la profondeur des données que tu possèdes, cela doit être une donnée gérée en parallèle.

c'est ce que j'avais essayé de faire, mais je dois pas etre doué.. de maniere evidente, je dois incrementer ma variable quand j'empile des données. par contre, quand je sors des données, je ne dois pas decrementer a chaque fois.. a priori, le probleme est simplifié vu que j'ai une recursion binaire..

en gros, si je vous suis, je peux imaginer un truc du genre :
sinon, j'avais pensé gere une deuxieme pile qui contiendrait les profondeurs respectives.. ca se ramene simplment au cas d'une recursion "normale", mais ca me semble un peu viloent...

merci a vous !

Code : Tout sélectionner

Pile P empiler(element de depart) profondeur <-- 0 tant que la pile n'est pas vide A<-- depiler(P) si A verifie une certaine condition, il est stocké (ou viré) *profondeur ???* sinon, couper A en 2 : A1 et A2 empiler(A1), empiler(A2), *profondeur++* fin tant que

Ta profondeur s'incrémente quand tu fais ton appel récursif, elle se décrémente quand tu sors d'un appel récursif. Donc incrémenter avant l'appel, décrémenter après : Mais si tu ne travailles pas réellement en récursif, ces raisonnements ne sont pas valables. La dérécursivisation d'un algorithme ne se fait qu'à la fin quand celui-ci est fonctionnel. Si tu pseudo-codes en récursif, que toute ta reflexion est sur du récursif, dans le but de produire un code non-récursif ça ne collera pas

en fait, je me base sur un algo dont "l'esprit" est recursif (on coupe en 2 et on analyse chaque moitie recursivement), sauf que la version en pseudo code sur laquelle je me base ( que j'ai repris telle quelle a partir d'un article) gere la pile "manuellement" l'algo est un peu long, mais le pseudo code que je donne au debut correspond assez bien... donc l'algorithme est bien iteratif, mais la notion de profondeur a un sens ( c'est pas clair, hein ? )

du coup, je ne comprend pas bien ce que tu me donnes. il me semble que ca marcherais si "empile" etait un appel recursif, ce qui n'est pas le cas..