La Place des Développeurs Récursivité en Basic
Bonjour
Je vous envoie un article paru dans le N°4 de MSX NEWS (juillet 87). Il commente un programme probablement envoyé par un lecteur pour gagner des bons d'achat et qui n'a pas été cité.
recursif.doc
Est-ce le bon sous forum ou fallait-il le mettre à ECOLE? Edité par antoin Le 23/11/2011 à 10h18
Je vous envoie un article paru dans le N°4 de MSX NEWS (juillet 87). Il commente un programme probablement envoyé par un lecteur pour gagner des bons d'achat et qui n'a pas été cité.
recursif.doc
Est-ce le bon sous forum ou fallait-il le mettre à ECOLE? Edité par antoin Le 23/11/2011 à 10h18
SANYO PHC-28l
Il est bien placé, pas de souci. 
Par contre, je ne saisis pas trop l'intérêt du programme, pour le calcul d'une factorielle, rien de tel qu'une bonne boucle FOR NEXT, là passer par un tableau pour faire ça, pfff...
Par contre, je ne saisis pas trop l'intérêt du programme, pour le calcul d'une factorielle, rien de tel qu'une bonne boucle FOR NEXT, là passer par un tableau pour faire ça, pfff...
MSX un jour, MSX toujours !
La factorielle n'est qu'un exemple simple.
tu trouveras plus d'explications sur l'intérêt de la récursivité dans:
http://fr.wikipedia.org/wiki/Algorithme_récursif
et aussi
http://www.siteduzero.com/tutoriel-3-36703-la-recursivite.html
Mon propos était + simple, montrer que bien que le basic ne soit pas récursif comme d'autres langages on pouvait contourner cette contrainte par un sous programme de quelques lignes.
D'ailleurs j'ai bien envie de développer cette rubrique qui pourrait s'intituler : contourner les limites avec le BASIC. dans ce premier exemple on contourne l'absence de récursivité; dans le prochain exemple comment dépasser les limites des calculs sur les entiers en basic? Edité par antoin Le 23/11/2011 à 11h23
tu trouveras plus d'explications sur l'intérêt de la récursivité dans:
http://fr.wikipedia.org/wiki/Algorithme_récursif
et aussi
http://www.siteduzero.com/tutoriel-3-36703-la-recursivite.html
Mon propos était + simple, montrer que bien que le basic ne soit pas récursif comme d'autres langages on pouvait contourner cette contrainte par un sous programme de quelques lignes.
D'ailleurs j'ai bien envie de développer cette rubrique qui pourrait s'intituler : contourner les limites avec le BASIC. dans ce premier exemple on contourne l'absence de récursivité; dans le prochain exemple comment dépasser les limites des calculs sur les entiers en basic? Edité par antoin Le 23/11/2011 à 11h23
SANYO PHC-28l
Je connais effectivement la récursivité, à l'époque où j’étudiais le Pascal et le C à l'université j'en ai pour ainsi dire bouffé ! 
Ceci dit, tu contournes effectivement une limite, mais tu monopolises des ressources de la RAM en utilisant un tableau. C'est résoudre un problème en en créant un autre, si tu vois ce que je veux dire (surtout avec des grands nombres) !
En tout cas, j'attends tes exemples suivants avec intérêt !
Ceci dit, tu contournes effectivement une limite, mais tu monopolises des ressources de la RAM en utilisant un tableau. C'est résoudre un problème en en créant un autre, si tu vois ce que je veux dire (surtout avec des grands nombres) !
En tout cas, j'attends tes exemples suivants avec intérêt !
MSX un jour, MSX toujours !
Moi aussi j'attends des exemples j'ai toujours eu un peu de mal avec la récursivité...
Cela peut s'appliquer à un jeu comme Puyo Puyo par exemple, pour définir les "blocs" de même couleur en contact, me trompe-je.
Cela peut s'appliquer à un jeu comme Puyo Puyo par exemple, pour définir les "blocs" de même couleur en contact, me trompe-je.
Le MSXien le plus à l'ouest
... ou presque 
Visiteur
Vagabond
Message : 0
On utilise le plus souvent la récursivité pour parcourir des graphes. Ça va de la compression de données au tracé de fractales en passant par la résolution d'un sudoku, ou la mise en place d'un minimax dans un jeu de réflexion (échecs, puissance 4… ) .
Pour des explications claires, cf le grand classique «structure and interpretation of computer programs» (Abelsson & Sussman).
Les auteurs l'ont mis à disposition gratuitement :
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1
Les exemples sont donnés en Scheme (une évolution de Lisp), mais restent bien plus lisibles que le programme basic du début.
Le problème du basic MSX, c'est que le «gosub» n'est pas ré-entrant et du coup il faut gérer la pile d'appels soi-même. Une simple factorielle va donner un mal de crane tenace, et pas la peine de songer à faire plus compliqué sans tomber dans le style «cuir et fouet». Edité par Visiteur Le 24/11/2011 à 11h36
Pour des explications claires, cf le grand classique «structure and interpretation of computer programs» (Abelsson & Sussman).
Les auteurs l'ont mis à disposition gratuitement :
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1
Les exemples sont donnés en Scheme (une évolution de Lisp), mais restent bien plus lisibles que le programme basic du début.
Le problème du basic MSX, c'est que le «gosub» n'est pas ré-entrant et du coup il faut gérer la pile d'appels soi-même. Une simple factorielle va donner un mal de crane tenace, et pas la peine de songer à faire plus compliqué sans tomber dans le style «cuir et fouet». Edité par Visiteur Le 24/11/2011 à 11h36
Le principe de récursivité m'a servi dans mon éditeur de map de King's Valley 2 pour définir si un écran dans la grille 6x6 était ou pas ajoutable/supprimable en fonction de son emplacement, sachant que tout les écrans actifs doivent être contiguë.
Peg'
Peg'
Rétro ... mais pas trop !
Alors récursivité possible en Basic ou pas La question reste, si on pouvait en faire un exemple sur un puissance 4 par exemple
La question reste, si on pouvait en faire un exemple sur un puissance 4 par exemple
Le MSXien le plus à l'ouest
... ou presque
Pour ceux que ça intéresse, la récursivité consiste à créer une fonction auto-appelante, c'est à dire qu'elle se déclenche elle-même.
Ce système est très utile dans les parcours d'arborescence ou les recherches de chemin (pathfinders) dans les jeux, par exemple.
Comme expliqué plus haut, j'ai eu besoin de cette technique pour la mise en place de la minimap de l'éditeur de niveau de King's Valley 2.
Les obligations sont les suivantes :
- activer des cases sur une grille 6x6
- chaque case activé doit être limitrophe à une autre
- toutes les cases doivent être interconnectée et former un seul et uniquement ensemble
Activation/désactivation d'une case :
Pour permettre l'activation d'une case, il suffit de vérifier que l'une se trouvant près d'elle (haut, bas, gauche et droite) est déjà activer pour l'autoriser.
Mais la désactivation d'une case ne doit pas engendrer de sous-ensembles.
Et c'est dans ce dernier cas que ça devient coton :
Si on prend une série de 3 cases, alignées horizontalement et que l'on supprime celle au centre, il nous restera deux sous ensemble.. ce que l'on ne désire pas.
Il est quasiment impossible de gérer ce genre de cas sans avoir retours au principe de fonction récursive.
Principe de Récursivité :
Il faut déjà savoir deux choses :
- une case est désactivée par défaut et contient 0 (false) ou 1 (true), selon la technologie de programmation choisie.
- Les tableaux sont à une dimension, évitant les imbrications de boucles (X=n%width, Y=int(n/width), n=X+(Y*width)).
La fonction récursive se déclenche à chaque case activée et se propage aux autres cases qui l'entoure, tout comme de l'eau qui s'écoulerait dans un réseau de tuyaux.
- Le principe est de créer un tableau logique vide de taille équivalente à l'aire de jeu
- Trouver la première case active
- Tester les 4 cases autours de cette case, puis de lancer une fonction sur chaque case active trouvée.
Ce principe va se propager comme une trainée de poudre en activant logiquement les cases testées.
Il ne restera qu'à comparer le tableau obtenu à celui existant et de voir si toutes les cases correspondent.
un exemple :
partons donc du principe que nous avons le schéma de base suivant.
Tout d'abord, on part d'une grille de taille équivalente, mais vide
1. La première case trouvée est la case 5. On l'active (noir), teste les cases autours. Seule la case 10 est active dans le tableau de référence (vert)
2. Une fonction est alors lancée sur la case 10 (qui est activée). Elle cherche aussi les cases alentours. la case 5 ayant déjà été testée, on ne la re-teste pas. La case 11 est donc lancée.
3. Tout comme dans l'étape précédente, mais sur la case 11. il en ressort la case 12.
4. La case 12 est testée, et deux cases sont alors actives. Soit deux chemins A et B
5. A (case 7) et B (case 17) sont donc testés chacune par une fonction, les cases 8 et 18 sont lancées en test.
6. Le test de la case 8 ne donne aucune case à tester et c'est donc la fin du chemin A. Le chemin B fait tester la case 23.
7. Le chemin B ne lance plus aucune fonction et se termine donc.
8. Le schéma résultant est donc comparé à celui de base. Ils correspondent et est donc valide !
Un autre exemple nous montre qu'amputé de la case 18, le schéma ne correspond plus :
La fonction récursive permet donc de tester le groupement des cases et détermine si toutes les cases sont interconnectées ou pas.
Peg'
ps: pour info, même si King's Valley 2 gère l'activation correcte des cases, il ne prend pas en compte la désactivation des cases permettant la création de deux groupes distincts.
Ce système est très utile dans les parcours d'arborescence ou les recherches de chemin (pathfinders) dans les jeux, par exemple.
Comme expliqué plus haut, j'ai eu besoin de cette technique pour la mise en place de la minimap de l'éditeur de niveau de King's Valley 2.
Les obligations sont les suivantes :
- activer des cases sur une grille 6x6
- chaque case activé doit être limitrophe à une autre
- toutes les cases doivent être interconnectée et former un seul et uniquement ensemble
Activation/désactivation d'une case :
Pour permettre l'activation d'une case, il suffit de vérifier que l'une se trouvant près d'elle (haut, bas, gauche et droite) est déjà activer pour l'autoriser.
Mais la désactivation d'une case ne doit pas engendrer de sous-ensembles.
Et c'est dans ce dernier cas que ça devient coton :
Si on prend une série de 3 cases, alignées horizontalement et que l'on supprime celle au centre, il nous restera deux sous ensemble.. ce que l'on ne désire pas.
Il est quasiment impossible de gérer ce genre de cas sans avoir retours au principe de fonction récursive.
Principe de Récursivité :
Il faut déjà savoir deux choses :
- une case est désactivée par défaut et contient 0 (false) ou 1 (true), selon la technologie de programmation choisie.
- Les tableaux sont à une dimension, évitant les imbrications de boucles (X=n%width, Y=int(n/width), n=X+(Y*width)).
La fonction récursive se déclenche à chaque case activée et se propage aux autres cases qui l'entoure, tout comme de l'eau qui s'écoulerait dans un réseau de tuyaux.
- Le principe est de créer un tableau logique vide de taille équivalente à l'aire de jeu
- Trouver la première case active
- Tester les 4 cases autours de cette case, puis de lancer une fonction sur chaque case active trouvée.
Ce principe va se propager comme une trainée de poudre en activant logiquement les cases testées.
Il ne restera qu'à comparer le tableau obtenu à celui existant et de voir si toutes les cases correspondent.
un exemple :
partons donc du principe que nous avons le schéma de base suivant.
Tout d'abord, on part d'une grille de taille équivalente, mais vide
1. La première case trouvée est la case 5. On l'active (noir), teste les cases autours. Seule la case 10 est active dans le tableau de référence (vert)
2. Une fonction est alors lancée sur la case 10 (qui est activée). Elle cherche aussi les cases alentours. la case 5 ayant déjà été testée, on ne la re-teste pas. La case 11 est donc lancée.
3. Tout comme dans l'étape précédente, mais sur la case 11. il en ressort la case 12.
4. La case 12 est testée, et deux cases sont alors actives. Soit deux chemins A et B
5. A (case 7) et B (case 17) sont donc testés chacune par une fonction, les cases 8 et 18 sont lancées en test.
6. Le test de la case 8 ne donne aucune case à tester et c'est donc la fin du chemin A. Le chemin B fait tester la case 23.
7. Le chemin B ne lance plus aucune fonction et se termine donc.
8. Le schéma résultant est donc comparé à celui de base. Ils correspondent et est donc valide !
Un autre exemple nous montre qu'amputé de la case 18, le schéma ne correspond plus :
La fonction récursive permet donc de tester le groupement des cases et détermine si toutes les cases sont interconnectées ou pas.
Peg'
ps: pour info, même si King's Valley 2 gère l'activation correcte des cases, il ne prend pas en compte la désactivation des cases permettant la création de deux groupes distincts.
Rétro ... mais pas trop !
Répondre
Vous n'êtes pas autorisé à écrire dans cette catégorie