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:
 

 
Merci d'avance pour votre aide !

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.

C'est bien ce qu'il me semblait :

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.

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

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" ?

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...