Stack OverFlow et les joies de la récursivité

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Stack OverFlow et les joies de la récursivité

Noxalus

Bonjour à toutes et à tous !

J'ai réussi il y a peu de temps à coder un algorithme de génération de labyrinthes parfaits. Celui-ci fonctionne très bien, mais comme j'ai utilisé la récursivité, celui-ci arrive rapidement en dépassement de mémoire, et je ne peux pas générer des labyrinthe de plus de 80*80. En effet, la pile d'appel à la fonction devient tellement grand qu'elle dépasse sa capacité maximum.

J'ai entendu dire qu'il fallait passer en itératif pour résoudre ce problème, mais je ne vois pas du tout comment faire. Faudrait connaître le nombre d'appel à la fonction, non ?

Je vous met la fonction "principale" qui est appelée à à répétition et qu'il faudrait modifier:

Citation :

/** Génére un layrnithe parfait **/
public void GenLabyParfait()
{
// On réinitialise le tableau
for (int i = 0; i < 4; i++)
{
casespossibles[i] = false;
}
// On recherche les cases possibles
casespossibles = RechercheCasesPossibles();

int j = 0;
for (int i = 0; i < 4; i++)
{
if (casespossibles[i] == false)
j++;
}
// Si aucune case n'est possible
if (j == 4)
{
// On regarde qu'on se retrouve pas à la case initiale
// (auquel cas la génération du labyrinthe est finie)
if (!(pos_actuelle == sortie_position))
{
// On retourne à la case précédente
pos_actuelle = pos_prec.Pop();
// Et on rappelle l'algorithme de génération avec la nouvelle position
GenLabyParfait();
}
}
// Si au moins un case est possible
// => on en choisi une au hasard
else
{
int mur_alea = random.Next(4);
while (casespossibles[mur_alea] == false)
{
mur_alea = random.Next(4);
}

// Haut
if (mur_alea == 0)
{
// On pose un chemin
Carte[pos_actuelle.X, pos_actuelle.Y - 1] = 0;
// On stocke notre position actuelle
pos_prec.Push(pos_actuelle);
// On avance sur cette case
pos_actuelle.Y--;
}
// Droite
else if (mur_alea == 1)
{
// On pose un chemin
Carte[pos_actuelle.X + 1, pos_actuelle.Y] = 0;
// On stocke notre position actuelle
pos_prec.Push(pos_actuelle);
// On avance sur cette case
pos_actuelle.X++;
}
// Bas
else if (mur_alea == 2)
{
// On pose un chemin
Carte[pos_actuelle.X, pos_actuelle.Y + 1] = 0;
// On stocke notre position actuelle
pos_prec.Push(pos_actuelle);
// On avance sur cette case
pos_actuelle.Y++;
}
// Gauche
else if (mur_alea == 3)
{
// On pose un chemin
Carte[pos_actuelle.X - 1, pos_actuelle.Y] = 0;
// On stocke notre position actuelle
pos_prec.Push(pos_actuelle);
// On avance sur cette case
pos_actuelle.X--;
}
// Et on rapelle l'algorithme
GenLabyParfait();
}
}

Merci d'avance pour votre aide !

Publicité

olivthill

Désolé, je n'ai pas la solution parce que, à première vue, ça a l'air un peu compliqué de transformer cet algorithme pour qu'il n'utilise pas la récursivité, alors que ce serait facile, si c'était un programme de calcul d'une factorielle.

Mais, pourquoi avoir choisi le langage C# au lieu du langage C pour faire ce genre de choses ? En C, non seulement, ce serait plus rapide, et plus économique en espace réservé sur la pile, mais de plus la taille de la pile est paramètrable. Il n'y aurait pas ce problème pour générer de grands labyrinthes, car la limite pour la pile qui existe sur les machines 32 bits ne serait probablement jamais atteinte, car avant cela, vous auriez probablement un autre problème qui serait la limite au niveau de la mémoire générale.

MagicBuzz

C'est bien ce qu'il me semblait :

Citation :

The default stack size for a thread is 1 MB, if you're running under the default CLR. However, other hosts may change that. For example the ASP host changes the default to 256 KB. This means that you may have code that runs perfectly well under VS, but breaks when you deploy it to the real hosting environment.

Fortunately you can specify a stack size, when you create a new thread by using the correct constructor. In my experience it is rarely necessary, but I have seen one case where this was the solution.

You can edit the PE header of the binary itself to change the default size. This is useful if you want to change the size for the main thread. Otherwise I would recommend using the appropriate constructor when creating threads.

En .NET aussi on peut changer la taille du stack.

Ceci dit, d'après ce que j'ai pu lire ici http://stackoverflow.com/questions [...] rsion-in-c si on arrive a faire des stack overflow en .NET, on est mal parti pour avoir un code qui tourne correctement, cette limite étant visiblement très grande (10000 appels comme ordre de grandeur, je trouve que c'est pas mal)

Sinon, +1 pour le choix du langage. Pas pour les mêmes raisons, mais simplement parce que je vois pas l'intérêt de faire du C# si c'est pour parcourir des tableau plutôt que d'utiliser des objets qui font ça à ta place... Même du C++ semble superflu dans ce cas précis, y'a même pas un seul appel à un seul objet.

Message édité par MagicBuzz le 28-01-2010 à 10:35:28

rufo

Pas me confondre avec Lycos!

Je vois pas de déclaration de variables (je pense à pos_actuelle) : dois-je en déduire qu'elles sont globales?
Pour transformer du récursif en itératif, en gros tu utilises un tableau qui va contenir des objets à traiter. Ensuite, tu définis 2 indexes : l'index pointant sur l'objet en cours de traitement et l'index pointant sur l'endroit où va falloir ajouter les nouveau objets à traiter par la suite (pas forcément en fin de tableau donc).

Le traitement est terminé quand l'index courant est arrivé à la fin du tableau

---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta

Noxalus

Merci à tous pour vos réponses !

Pour le choix du langage, je suis en première année d'école d'ingénieur en informatique, et le langage est imposé pour notre projet de fin d'année (enfin, on a le choix entre C# et F#).

Pour l'augmentation de la pile des appels, j'ai aussi vu qu'on pouvait le faire, mais ce n'est pas vraiment la solution.

Sinon, j'ai effectivement passé toutes les variables en globales. Oui, j'ai pensé qu'à chaque appel de la fonction des variables été créées et que c'est ça qui prenait de la place.

Ton idée, Rufo, ressemble grossièrement à ce que notre prof d'algo m'a dit, c'est-à-dire gérer la pile d'appel nous même. Mais c'est justement ça que je n'ai pas compris

Qu'appelles-tu l'objet "en cours de traitement" ?

rufo

Pas me confondre avec Lycos!

Tu peux trouver un ex d'implémentation de cette méthode dans mon soft "Astres" (cf ma signature), la fonction getSubLevelsAowOfAow() qui se trouve dans le fichier DbAowLibrary.php du répertoire /Astres/Common/.

En gros, j'ai une arborescence de tickets (help-desk) : un ticket parent et des sous-tickets, chaque sous-ticket pouvant lui-même avoir des sous-tickets, ... comme ça, potentiellement sur 127 niveaux. La fonction permet de récupérer la sous-arbo de tickets d'un ticket donné.
Donc, je lance une requête SQL pour récupérer les sous-tickets du niveau juste en-dessous du ticket donné en entrée de la fonction. Je stocke les ID (ce sont mes "objets" ) des sous-tickets dans un tableau (ma pile). Mon objet en cours de traitement est donc l'ID du ticket donné en entrée.
Ensuite, j'avance d'un cran dans mon tableau (pile) pour récupérer les sous-tickets du 1er sous-ticket récupéré à l'étape précédente. Je stocke dans mon tableau, après l'ID du ticket en cours de traitement, mais avant le suivant dans le tableau, les nouveaux ID récupérés et ainsi de suite...

FORUM HardWare.fr

Programmation

C#/.NET managed

Stack OverFlow et les joies de la récursivité

Sujets relatifs
défilement horizontal avec la pté CSS overflow	Problème avec JSCalendar et overflow
[autotools] Makefile.am et recursivite	[résolu] Div en overflow:auto, garder le focus en bas ?
Recursivité et XSLT	Overflow: auto et scrollbar ie6
Probléme argv	Jeu "Le compte est bon" avec récursivité
[C] Stack Overflow
Plus de sujets relatifs à : Stack OverFlow et les joies de la récursivité

Page générée en 0.041 secondes