Gestion de la pile

Question

Bonjour à tous,
J'utilise une fonction récursive pour résoudre des expressions, mais me voila tombé sur des expressions plus complexes que je ne le pensais et j'obtiens des problèmes de StackOverflow, dépassement de la capacité de la pile si je ne me trompe... 
Je ne peux pas réécrire ma fonction en mode itératif car elle peut générer plusieurs branche différentes et je ne vois pas comment je pourrais faire...
Quel accès ai-je à la pile ? 
Je vois bien ce que c'est du coté algorithme, mais je ne sais pas où elle se trouve, dans la Ram ? Dans le Cache ? Une zone à part ?
Y-a-t'il moyen de la vider qque part pour pouvoir continuer ?
J'imagine que le nombre de fonction que je peux invoquer récursivement dépend du nombre et de la taille des paramètres de la fonction. Elle prend un objet en paramètre, mais en vb, il passe en réalité un pointeur de cet objet, je me trompe ?
Enfin voilà si vous avez une idée pour m'aider elle est la bienvenue...

Julien

cs_casy · Answer

Normalement la pile n'est pas accessible.
Si tu as un débordement c'est que tu as trop de récursivité dans tes appels, tu as trop de branches à traiter.

La vider? ni pense pas, si tu vide la pile, tu perd entre autre le point de retour des appels à ta fonction. Donc tu restera coincé à moitiée branche. Et de plus tu génerera une belle erreur système sur le retour de ta fonction, car tu tenteras de lire une donnée en pile, alors qu'il n'y en a plus. 

Pour limiter la casse, il faut reduire au maximun le nombre de variable que tu as dans ta fonction, réutiliser le plus possible les variables existantes plutot que d'en créer d'autres. Passe toutes les variable que tu peux en variables globales ou en statiques (mais dans une fonction récursive, tu ne doit normalement pas en voir beaucoup, voire aucune).

Par contre il est fort probable que VB2005 permet une gestion de pile, style augmentation de l'espace réservé pour la pile, mais je ne le connais pas assez pour te répondre.

Pour info : 
Est stocké en pile au minimum, tout le contexte du processeur lors de l'appel d'une fonction, l'adresse de retour lorsque la fonction est terminée, touts les paramètres passés à la fonction, la valeur de retour de la fonction, et aussi toutes les variables de la fonction qui ne sont ni statiques, ni globales (en gros les variables déclarée avec un simple Dim).

Donc si tu réentre 10 fois dans ta fonction (10 sous branches), tu multiplis tout ça par 10

---- Sevyc64  (alias Casy) ----<hr size="2" width="100%" /># LE PARTAGE EST NOTRE FORCE #

Julien237 · Answer

Oui c'est hélas ce que je pensais...
Pour la vider, je pensais, la stocker, continuer les fonctions, puis lorsque qu'il remonte la pile, la remettre à sa place...
A l'intérieur j'ai juste un double de déclarer et en paramètre j'ai un objet que j'ai défini, mais il n'en passe qu'un pointeur non ? Il n'empile pas tout l'objet ?
Sinon je peux toujours faire une pile à la main dans une boucle (en imitant le système du mieux que je peux :p)... Mais ca va être chaud !

Merci !

cs_casy · Answer

Je ne sais pas comment est déclaré ton objet en pile, mais il doit bien etre dupliquer quelque part. 
SI tu crée ton objet avec une instruction Dim dans ta fonction, à chaque nouvel appel de la fonction, c'est un nouvel objet qui est créé. il y a de forte chance que ce soit sur la pile.

---- Sevyc64  (alias Casy) ----<hr size="2" width="100%" /># LE PARTAGE EST NOTRE FORCE #

Julien237 · Answer

Non il est juste passé en paramètre, mais je peut le créer dans l'appel, en gros pour les variables, ont peut résumer ma fonction comme ceci :

Function Calcul(byref c as Capsule) as double
  Dim r as double
  ...
  Select case C.Operation
    case ....
    r = Calcul(new capsule(......)) [Opération] Calcul(new capsule(.....))
    'Ou selon les cas (le plus souvent d'ailleurs)
    r = Calcul(c.MembreGauche) [Opération] Calcul(c.MembreDroit)
    'MembreDroit et Gauche étant aussi des Capsules

  ...
  return r
end function

Mais je pense à une autre méthode : 
 - Je compte le nombre de fonction maximale que je peux invoquer (disons n)
 - Je commence normalement en comptant l'imbriquement de mes fonctions
 - Lorsque j'arrive à n-1, j'enregistre les paramètres que je devrais envoyer à la fonction n et je retourne un message défini disant d'attendre, jusqu'à la première fonction invoquée (remontant toutes les fonctions et vidant ainsi la pile)
 - J'invoque la fonction suivante avec les paramètres mémorisés et je retiens le résultat.
 - Je recommence depuis le début, et lorsque j'arrive à la fonction n-1, la fonction n est déjà calculée, je lui renvoie la valeur.

Va falloir mettre ca en place en comptant que le processus peut se faire plusieurs fois par branche d'invocation ^^

Merci pour tes réponses !

cs_DARKSIDIOUS · Answer

Si tu arrive à un stackoverflow, c'est qu'il y a vraiment beaucoup d'appels !
Es-tu sûr que tu ne tombe pas dans des appels récursif en boucle infini ?

Julien237 · Answer

Oui j'ai vérifié une immense partie à la main, ca me semble tout à fait correct.
En fait je suis toujours dans le projet de reprise d'excel que j'ai expliqué il y a quelques postes, et j'ai ce problème lorsque je calcul les cellules qui sont 'tout en haut' de l'arbre de référence si je puis dire... Elles dépendent de milliers de cellules très lourdement imbriquées d'où mon problème de StackOverflow quand y'en a trop....

Julien.

Gestion de la pile

6 réponses

Votre réponse

Discussions similaires