Discussion :

[Argol_Medusa]

Bonjour,

j'ai un problème dans un algorithme récursif.

j'ai une fonction qui s'appelle elle-même un nombre assez important de fois jusqu'à ce qu'elle trouve ce qu'elle recherche.

Le problème c'est que je me retrouve avec un "le projet machintruc.exe a provoqué une classe d'exception EStackOverflow avec le message 'Débordement de pile' "

Est-il possible d'augmenter la taille de la pile et si oui jusqu'à combien et surtout ... où est-ce que ça se trouve ??? dans les options de compilation ? je n'ai rien trouvé :o

[sat83]

As tu bien vérifier que ta condition d'arrêt de ta fonction récursive est correct?

[Argol_Medusa]

As tu bien vérifier que ta condition d'arrêt de ta fonction récursive est correct?

Pour être franc je me suis dis que si j'augmentais la taille de la pile de manière assez importante et que j'avais toujours le stack overflow c'est que ma condition d'arrêt est foireuse :p (c'est un moyen de vérifier cela ^^')

Donc j'ai pris le problème à l'envers, mais je vais regarder effectivement il faut mieux faire l'inverse.

Je vérifie ce point et j'édite mon message pour donner la réponse ^^'

Edit : Effectivement ma récursivité ne s'arrete jamais donc c'est pour cela que j'ai un stack overflow pour l'instant.


Mais est-il tout de même possible d'augmenter la taille de la stack (en prévision de la future stack overflow que j'aurai de toute façon même après avoir corrigé le bug de la condition de sortie ) ?

[Argol_Medusa]

Bon ma condition de sortie était foireuse et effectivement c'est bien cela qui me provoquait un stack overflow.
Mais par la suite même en empilant pas mal de récursivité je ne suis pas arrivé au stack overflow donc je pense que la stack est assez grosse.

Je mets le sujet en résolu mais je suis cependant toujours preneur de l'info sur la taille maxi de la stack sur le borland, et sur comment le modifier si quelqu'un l'a.*

Merci !

[koala01]

Salut,

Le sujet a beau être résolu, quelques conseils supplémentaires ne font jamais de tord

De manière générale, il est toujours préférable de choisir la solution qui consiste à s'assurer que la logique suivie (ici, la condition de sortie de la récursivité) soit correcte plutôt que d'envisager des "palliatifs" qui consistent à modifier la taille de la pile ou autres "idioties" du genre.

Si je parle d'idioties, c'est à dessein: tu ne fera jamais que "reculer pour mieux sauter".

En effet, si - par malchance - le fait d'augmenter la pile t'évite le "plantage" de l'application, cela ne fait que résoudre *très temporairement* le problème: la charge de travail en période de production étant bien souvent plus importante qu'en période de développement, ton application risque très fort... de planter lorsqu'elle sera en prod, avec des conséquences bien pire que le fait de perdre 2 heures à trouver l'origine d'un bug

D'un autre coté, si j'admets parfaitement l'idée des fonctions récursives (je suis sans doute l'un des rares qui n'en ait absolument pas peur et qui plaide pour leur utilisation), il est quand même toujours bon de rappeler que cette technique doit être utilisée avec parcimonie: Ce n'est pas parce qu'on peut l'utiliser (car on peut l'utiliser en remplacement d'une boucle "classique") qu'il faut l'utiliser.

Bien souvent, s'il y a "facilement" moyen d'arriver au résultat en utilisant une boucle "classique", c'est qu'il est fortement préférable... d'utiliser cette boucle classique (par boucle "classique", j'entend les boucle pour, tant que et jusqu'à: for(...;...;...), while(...) et do{}while(...) )

Je ne sais pas sur quoi tu travaille, et je n'ai donc absolument pas la prétention de dire que tu utilises la récursivité à mauvais escient, mais, es-tu sur que tu te trouve effectivement dans une situation où c'est la meilleure (ou à défaut, la moins mauvaise) des solution

Enfin, parce qu'une "piqure de rappel" n'est jamais inutile, n'oublie pas que, la règle de base, lorsque tu travaille sous forme récursive, c'est de tester "le cas de base", autrement dit de tester le cas dans lequel il n'y a plus d'appel récursif de la fonction.

Le reste de la logique aura alors pour but de veiller à "tendre vers le cas de base"

[henderson]

Salut !

D'un autre coté, si j'admets parfaitement l'idée des fonctions récursives (je suis sans doute l'un des rares qui n'en ait absolument pas peur et qui plaide pour leur utilisation),

Tu fais comment pour dénombrer les "rares" ?
A l'aide d'un raisonnement ad hoc ?

A plus !

[Argol_Medusa]

merci koala01 pour tous ces bons conseils.

Je suis d'accord avec toi à 100%.

Dans l'application que je développe, le but était avant tout de tester la faisabilité de la chose avant de commencer à coder le programme finale, on était donc au stade de "prototype" je dirais et d'ailleurs l'algo va être changé car c'est pas assez rapide.C'est pourquoi j'ai codé un peu "à l'arrache" sans vérifier mes conditions de sorties.

En fait je ne suis pas fan de récursivité du tout et il y a encore quelques semaines je disais que c'était une "connerie" mathématique qui ne sert à rien en pratique ... jusqu'à ce que je tombe sur ce cas de figure particulier :

une matrice 2 dimensions représentant une carte vu de dessus avec des chiffres représentant les difficultés qu'a un piéton pour traverser chaque case ( cellules élementaires ).

En gros j'ai une grille 2D avec des chiffres dessus, pour passer d'une case à une autre j'ajoute le chiffre de la case ( un temps de trajet), quel chemin doit-on prendre pour que notre route soit la plus rapide possible?

Et bien pour résoudre ce problème, ce n'est pas si simple que ça c'est le moins qu'on puisse dire.

J'ai cherché dans des ouvrages mathématiques si il existait une formule qui à partir d'une matrice [n;m] donnait le chemin le plus court entre deux point A et B ... que dalle

Donc l'algo que j'ai créé consiste à créer une fonction qui prend en entrée une position précédent (xprecedent, yprecedent), une position courante ( x,y ), qui calcule le temps de trajet effectué sur la case ( ajoute au temps_de_trajet_total la valeur de la matrice à la position (x,y) ), et appelle la même fonction (elle-meme) en lui donnant comme nouveau paramètre x,y la case de gauche, de droite, en haut et en bas.

Je ne suis pas DU TOUT un fan des récursivité mais je dois bien admettre que dans ce cas de figure précis, je ne sais pas si on peut s'en sortir autrement ( et de manière plus rapide surtout car pour une "carte" de 20x10 cases ça me prendre quand meme 3 minutes environs sur une bonne machine :s d'où mon algorithme que je vais changer pour optimiser tout ça ( il faut moins de 5 secondes au total

[koala01]

A vrai dire, il existe quelque algorithmes "habituels" pour la recherche d'itinéraires... as tu déjà jeté un oeil dessus

Dans la partie "algorithme" du site, tu devrais pouvoir trouver des informations sur le "path_finding" comme l'algorithme de Dijsktra ou l'algorithme "A*" (que l'on prononce " a star" )

Sauf erreur, tu devrais trouver des cours / tuto / ressources intéressantes pour résoudre ton problème

[cedni]

et moi je vais ajouter mon grain de sel .

n hesitez pas à poster du code , de moins en moins de monde le fait , on peut pas deviner .

Sinon ton algo m a l air interessant à coder , postes un bout de code un de ces quatre .

Bonne continuation .

[Argol_Medusa]

Merci à tous les deux pour votre aide et vos conseils.

On m'avait parlé de l'algorithme de machintruc ( Dijsktra ) mais je n'avais pas retenu le nom et du coup pour rechercher sur google c'était gallère

J'ai commencé à regarder dans le forum algorithme je pense que je vais m'orienter vers du A* car il serait plus rapide à priori mais je n'ai pas encore trouvé l'algorithme en question, je continue mes recherches et je posterai le bout de code une fois qu'il marchera et aura été testé.

[koala01]

tu peux déjà regarder sur le wikipedia qui fournit quelque informations "intéressantes" sur l'algorithme A*

Pour Dijkstra, tu peux aller voir du coté de l'article sur les algorithmes les plus courent de julien ou du coté de wikipedia (de nouveau)

Sois attentif au fait que A* considère que tous les déplacement se valent: on sait passer, ou non, alors qu'avec Dijkstra, tu peux donner des valeurs permettant de "peaufiner" le chemin (on préférera peut etre faire un déplacement plus long qui ne nous obligerait pas à sauter d'une hauteur de 10 metres )

[Argol_Medusa]

Ok, après lecture de tout ça je crois que j'ai compris l'algo A* ( dans ses grandes lignes en tout cas ) et ça correspond à peu pret à ce que j'avais imaginé instinctivement pour m'en sortir avec quelques nuances qui doivent accélérer le process je pense.

Le A* correspond mieux à ce que je veux faire que Dijkstra.

Bon ben ya plus qu'a, je code tout ça dès que j'ai 5 minutes et je vous tiens au courant

Encore merci à tous !