La récursivité en Basic Casio
Posté le 02/03/2016 20:10
La récursivité en Basic Casio est une chose qui a du mal à être appliquée, puisqu'on ne peut appeler un programme jusqu'à une profondeur d'environ 10, et qu'à cela s'ajoute le fait que les variables sont globales et non locales. L'astuce suivante consiste à combiner des boucles – ou des labels par lisibilité, vous verrez pourquoi – et utiliser les listes comme piles d'arguments, permettant ainsi d'aller jusqu'à 999 niveaux de profondeur.
Je prendrais l'exemple du pot de peinture récursif dans la suite, mais l'astuce est généralisable à tout algo récursif.
Voici l'algo en question :
1. Fonction peinture(x, y)
1. Colorier le pixel (x, y)
2.
3. Si le pixel(x+1, y) est éteint
4. Appeler peinture(x+1, y)
5. Si le pixel(x-1, y) est éteint
6. Appeler peinture(x-1, y)
7. Si le pixel(x, y+1) est éteint
8. Appeler peinture(x, y+1)
9. Si le pixel(x, y-1) est éteint
10. Appeler peinture(x, y-1)
11. Fin fonction
Analyse du comportement de l'interpréteur
Lorsque la fonction est appelée pour la première fois, elle allume le premier pixel, normal, et si la condition de la l.3 est vérifiée, elle s'appelle elle-même (l.4), mettant dans un coin les variables dont elle a eu besoin (x et y) pour utiliser les nouvelles (comportement local des variables). Elle rentre alors dans un nouveau niveau plus bas de récursivité. Une fois arrivée à la fin, c'est à dire si tout les pixels autour sont allumés, elle ressort en l.5 puis continue de s'exécuter mais un niveau plus haut.
L'astuce
L'idée consiste à utiliser n listes pour les n variables locales de notre fonction, une variable P qui servira à désigner la profondeur actuelle, et des conditions pour exécuter les bouts de code correspondants. Bon moi j'utilise ici des labels pour faciliter la compréhension du truc, mais un code 100% sans labels est réalisable (bien que plus lourd). De même, j'utilise qu'une unique liste et les complexes pour gérer x et y.
Voici donc le code que je vous propose :
// P est la profondeur de récursivité
1→P
// A est une variable "locale", qui dépend donc de P. C'est elle qui stocke x et y
64+32i→A
// On place un label au début de notre fonction.
Lbl 0
// On allume le pixel A (attention c'est inversé (PxlOn Y, X)
PxlOn Imp A, Rep A
// On teste si le pixel à droite est éteint (j'enlève ici les tests de sortie d'écran, ils sont dans le code final)
If Not PxlTest Im A, Re A+1
Then A→List 1[P] // On met sur la pile les variables "locales"
A+1→A // On modifie les variables "locales" pour le nouvel appel
1→List 2[P] // On sauvegarde l'endroit d'où on quitte la "fonction"
Isz P // On augmente un niveau de profondeur
Goto 0 // Et on saute au début
Lbl 1 // On n'oublie pas le label qui nous servira à continuer l'exécution
IfEnd
// On réitère les instructions dont on a besoin
// On teste si le pixel à gauche est éteint
If Not PxlTest Im A, Re A-1
Then A→List 1[P] // pile
A-1→A // nouvel argument
2→List 2[P] // saut de retour
Isz P // profondeur
Goto 0 // appel
Lbl 2 // position du saut de retour
IfEnd
…
// Un fois à la fin, si on est pas en haut, on remonte d'un niveau, et on saute à l'endroit d'où on est parti
If P>1
Then Dsz P // On remonte d'un niveau
List 1[P]→A // On récupère les variables de la pile pour les mettre en "local"
List 2[P]=1⇒Goto 1 // Suivant l'endroit duquel on est parti, on saute à l'endroit correspondant
List 2[P]=2⇒Goto 2
List 2[P]=3⇒Goto 3
List 2[P]=4⇒Goto 4
"FIN" // Ici on est hors fonction
Bien entendu, on peut se passer des labels moyennant une boucle et pas mal de conditions, et mettre le tout dans un sous-programme.
Ci-joint le programme d'exemple, à vous de stoker une picture (1) puis de donner sous la forme X+iY les coordonnées d'application du pot de peinture.
Si vous avez des questions, n'hésitez pas à les poser, le topic est fait pour ça.
Louloux a écrit :
L'astuce réside donc en fait dans le fait d'utiliser n listes pour simuler les n variables locales.
C'est assez intéressant, bien que limitant en nombre de variables, mais le Basic Casio est déjà ultra limité pour ça, donc ça ne change pas grand-chose.
Un autre problème est dans le retour à l'endroit où on a effectué l'appel récursif, pour ça tu te débrouilles bien mais ça fait un code long et assez sale.
Bref, c'est intéressant mais perd l'avantage de la simplicité et de l'élégance de la récursivité, qui n'a pas beaucoup de sens dans un langage impératif et pas du tout du tout fonctionnel. Autant utiliser, quand c'est possible, un algorithme impératif.
Fichier joint
Citer : Posté le 02/03/2016 20:48 | #
L'astuce réside donc en fait dans le fait d'utiliser n listes pour simuler les n variables locales.
C'est assez intéressant, bien que limitant en nombre de variables, mais le Basic Casio est déjà ultra limité pour ça, donc ça ne change pas grand-chose.
Un autre problème est dans le retour à l'endroit où on a effectué l'appel récursif, pour ça tu te débrouilles bien mais ça fait un code long et assez sale.
Bref, c'est intéressant mais perd l'avantage de la simplicité et de l'élégance de la récursivité, qui n'a pas beaucoup de sens dans un langage impératif et pas du tout du tout fonctionnel. Autant utiliser, quand c'est possible, un algorithme impératif.
Citer : Posté le 02/03/2016 20:59 | #
Bonne conclusion
Mais c'est faisable.
Citer : Posté le 05/03/2016 14:20 | #
Voilà un tuto plus intéressant... malgré l'absence de récursivité réelle en Basic Casio, ça peut rester pratique (le pot de peinture itératif, euh...)
Citer : Posté le 05/03/2016 18:13 | #
Ben, en itératif c'est assez du de traiter tout les cas. Ça se fait, mais c'est bordélique. Et puis la version récursive est facile à comprendre et plus complexe qu'une simple factorielle.
Citer : Posté le 05/03/2016 18:42 | #
Bien vu le Goto 0:Lbl 1
Citer : Posté le 05/03/2016 20:44 | #
(le pot de peinture itératif, euh...)
Enfiler (xi,yi) dans F
Tant que F est non vide:
Défiler (x,y) de F
Pour (x2,y2) parmi (x-1,y), (x+1, y), (x,y-1), (x,y+1):
Si (x2,y2) est éteint:
Allumer (x2,y2)
Enfiler (x2, y2) dans F
Les couples se représentent par des complexes, la file par une List (dont on garde la taille et l'indice de début dans deux variables, et on fonctionne avec des modulos).
Citer : Posté le 05/03/2016 22:23 | #
Ben oui mais si t'utilise une file c'est comme si tu fais de la récursivité : la récursivité c'est placer les adresses de retour sur la pile, rien d'autre... x)
Donc là je parlais d'un algorithme sans liste (enfin pas de la manière dont tu l'as utilisée en tout cas).
Citer : Posté le 05/03/2016 23:20 | #
Mon algo est tout à fait impératif -au fait please dites pas itératif parce que le récursif est tout aussi itératif-, et son implémentation relativement propre en Basic par rapport à une simulation de récursivité avec des Lbl/Goto. Ce que j'essayais de dire ce qu'on se débrouille souvent pour remplacer du récursif en utilisant les structures de données appropriées.
Ajouté le 05/03/2016 à 23:22 :
Pour ceux qui ne connaissent pas trop les notions de prog impérative et fonctionnelle :
Programmation impérative
Programmation fonctionnelle
Citer : Posté le 05/03/2016 23:23 | #
-au fait please dites pas itératif parce que le récursif est tout aussi itératif-
Bon ben justement, si le récursif est aussi itératif, parce que ce qui compte c'est les structures de données, on peut pas vraiment dire qu'en passant de la pile du programme à une file dans une liste, t'aies trop changé l'algo... tu fais exactement les mêmes tests et le même raisonnement : pour moi c'est le même algo.
Citer : Posté le 05/03/2016 23:30 | #
Ben euh évidemment que c'est le même algo, c'était mon but. Je voulais montrer qu'on pouvait écrire cet algo sans recourir à une simulation de récursivité, et de manière plus générale que tout algo s'écrit très bien avec nos boucles chéries, sans recourir à des Lbl/Goto, et de manière plus propre.
Citer : Posté le 05/03/2016 23:32 | #
Ok, alors c'est moi qui me suis mal exprimé :
(le pot de peinture itératif, euh...)
Comprenez par là : un algorithme de pot de peinture qui n'utilise pas de structure assimilable à de la récursivité (et donc pas l'analyse des quatre pixels adjacents) me semble difficile à concevoir.
Citer : Posté le 05/03/2016 23:33 | #
Cf ma conclusion puisque le but de ce topic était de présenter à ceux qui me l'ont demandé comment simuler du récursif en Basic. Et par la même occasion de montrer que c'est rarement approprié.
Citer : Posté le 05/03/2016 23:36 | #
le but de ce topic était de présenter à ceux qui me l'ont demandé comment simuler du récursif en Basic. Et par la même occasion de montrer que c'est rarement approprié.
Yep, je pense que si j'ai le courage je ferai, un de ces jours, un tuto sur l'implémentation Casio de différentes structures de données intéressantes et leur utilité (histoire d'ouvrir des possibilités à ceux qui n'ont pas de grosses connaissances algorithmiques car autodidactes de l'info)