Oniromancie: Tutoriels - EMG 7 : La récursivité


Comment ça marche?

Aëdemphia
Par Sylvanor

Fighting Robots Quest
Par Boulon

Forstale
Par Ødd Clock

Geex
Par roys

Inexistence
Par Falco

La Légende d'Ibabou
Par Zaitan

Lije
Par Gaetz

LoveMaster
Par Cuddlefox

Sarcia
Par Kaëlar

Super Mario RPG - Lost Souls
Par Omegabowser

Alex d'Or 2017-18: règlement / News: MegaMaker : créez votre propre (...) / News: Test de Tinker Quarry / Sorties: Leave the Room / Jeux: Leave the Room /

Chat  (13 connectés)

Bienvenue
visiteur !






publicité RPG Maker!

Statistiques

Liste des
membres


Contact

69 connectés actuellement

9170552 visiteurs
depuis l'ouverture

804 visiteurs
aujourd'hui

Groupe Facebook

Barre de séparation

Partenaires




TOP
GAMEMAKING


Les 5 plus
visités

Lunae, le baz'arts d'Emz0

Le studio du chat vert

Pixelandgame

Tashiroworld

HeyMakeGames

Au hasard

Making4Life

Lunae, le baz'arts d'Emz0

Metal Gear RPG

Les deux derniers

Lunae, le baz'arts d'Emz0

Le studio du chat vert

Nos autres partenaires

Devenir
partenaire


Barre de séparation

Un site du réseau
War Paradise

Annuaires référenceurs





EMG 7 : La récursivité
Ecrit par François Berhn

I Introduction
Ce tutoriel fonctionne pour tous les RM.

Si c'est le premier tutoriel de la série que vous lisez, je vous conseille fortement de lire les précédents qui sont des aides à la compréhension de ce tutoriel.

II Concept
La récursivité désigne un morceau de code qui fait référence à lui même, que ce soit directement dans lui-même ou par un autre morceau de code qu'il appelle (aka le premier execute le seconde qui execute le premier). Cette technique est souvent opposée à la méthode itérative qui préfèrera jouer sur les effets de bord là ou la récursivité se base plutôt sur le retour de valeur.

III Exemple
Pour donner un exemple, reprenons le code du premier tuto sur le calcul de puissance :

Portion de code : Tout sélectionner

1
2
3
4
5
6
7
8
9
10
11
12
def power(nombre, puissance)
  accumulateur = 1
  while true
    if puissance == 0
      break
    end
    accumulateur *= nombre
    puissance -= 1
  end
  return accumulateur
end
puts power(2, 3)



Ici il s'agit d'une méthode itérative car non seulement il n'y a pas appel de la fonction dans son propre corps mais en plus on utilise la variable puissance pour compter le nombre de fois que la boucle va s'effectuer (on réduis sa valeur petit à petit et une fois qu'elle atteint 0, on quitte la boucle).

Voici maintenant son équivalent récursif :


Portion de code : Tout sélectionner

1
2
3
4
5
6
7
def power(nombre, puissance)
  if puissance == 0
    return 1
  else
    return nombre * power(nombre, puissance - 1)
end
puts power(2, 3)



On remarque alors que le code est plus court, pour un même calcul (même s'il faut garder en tête que les deux versions n'ont pas été compactées le plus possible).

Je ne pense pas avoir à vous expliquer le fonctionnement de la méthode itérative. penchons-nous cependant sur la méthode récursive.
Admettons que je veuille calculer 2**5 (aka deux à la puissance cinq). Ce qu'on sait c'est qu'on peut remplacer cette écriture par celle-ci :

2*2*2*2*2 avec autant de 2 que que le nombre de la puissance (ici 5). Hors en modifiant légèrement ce calcul on peut obtenir ceci :

2*(2*2*2*2) dont on remarque que le calcul entre parenthèses n'est autre que la définition de 2**4. Et on peut répéter le processus ainsi pour constater que 2**4 c'est 2*(2**3) :

2*(2*(2*(2*(2*(1))))

De fait, il est possible de généraliser le calcule de la puissance comme ceci :
Pour tout x :
x ** 0 vaut 1
x ** n vaut n * (x ** (n-1))

On peut constater d'ailleurs qu'un définition récursive possèdes au moins deux cas différents à gérer : Le cas avec n pour l'appel récursif et le cas avec 0 pour stopper la boucle récursive

Enfin bon c'est beau tout ça mais il faudrait voir ce que ça donne en event.

IV En event
Si la récursivité peut-être intéressante, elle a malheureusement besoin de variables locales pour être utilisées. En effet, si on reprend l'exemple dessus pour calculer 2**5 il faut qu'il calcule au préalable 2**4 pour le multiplier par 2, ce qui implique de calculer 2**3 pour aussi le multiplier par 2, etc...

Ce que va donc faire l'ordinateur c'est lancer le calcul de 2**5 qui va lancer le calcul de 2**4 qui va lancer le calcul de 2**3 qui va... lancer le calcul de 2**0. Ce dernier calcul va alors retourner 1 qui va être récupéré par le calcul de 2**1 pour le multiplier par 2 et le retourner puis 2**2 va effectuer la même chose à ce retour et ainsi de suite jusqu'à ce que la fonction qui calcule 2**5 retourne le bon résultat.

Ce qu'il faut retenir de ceci, c'est qu'à un moment, tous les calculs de puissances invoqués sont présents en mémoire au même moment. Il est donc indispensable que les variables nombre et puissance soient locales à la fonction qui les utilise pour ne pas avoir des collisions.

De fait, est-il possible de reproduire cette fonction dans RM ? Non. Mais il est possible de contourner le problème.
En effet, comme les events communs n'ont ni paramètres ni retour le seulement moyen d'aborder le problème est de passer par les effets de bord. Ainsi voici une solution au problème :

image

En fait ce que fait ce code c'est :

Le première condition vérifie que c'est la première execution du programme et si ce cas initialise une variable en la mettant à 1.
Et la seconde condition regarde s'il y a encore besoin de multiplier le résultat et d'appeler l'event commun. Si ce n'est pas l'interrupteur est désactivé et on sort de la boucle récursive.

Pour faciliter la comparaison, voici la version itérative utilisée dans le premier tuto :

image

On se rend compte que le code itératif est actuellement plus compact, mais il serait en fait possible de raccourcir le code récursif en appelant un premiert event commun qui initialise le résultat à 1 et qui en appelle un second faisant le calcul récursif. De fait il n'y aurait plus besoin de conditions utilisant l'interrupteur.

Aussi, le code peut, quand il n'utilise pas plus de variables que ses arguments devenir plus compact, en atteste ce code qui réimplémente le modulo :

image

Et je pense qu'il sera plus facile de vous expliquer le fonctionnement avec cet event là.
En fait ce qu'il faut comprendre c'est qu'un event commun n'est finalement qu'une séquence d'instructions mire de côté pour pouvoir être exécutée à la demande. De fait dans notre cas si on voulait utiliser cet event commun pour calculer 11 % 2 il se passerais :
- 11 est supérieur ou égal à 2 ? Oui
- On lui retranche 2 -> il reste 9
- On appelle l'event commun qui va refaire ce qui a été fait jusque là mais avec 9
- 9 est supérieur ou égal à 2 ? Oui
- On lui retranche 2 -> il reste 7
- On appelle l'event commun qui va refaire ce qui a été fait jusque là mais avec 7
- 7 est supérieur ou égal à 2 ? Oui
- On lui retranche 2 -> il reste 5
- On appelle l'event commun qui va refaire ce qui a été fait jusque là mais avec 5
- 5 est supérieur ou égal à 2 ? Oui
- On lui retranche 2 -> il reste 3
- On appelle l'event commun qui va refaire ce qui a été fait jusque là mais avec 3
- 3 est supérieur ou égal à 2 ? Oui
- On lui retranche 2 -> il reste 1
- On appelle l'event commun qui va refaire ce qui a été fait jusque là mais avec 1
- 1 est supérieur ou égal à 2 ? Non
- Il ne reste plus rien à faire et les events communs s'arrêtent
On constate donc bien que 11 % 2 = 1

V Conclusion
Dans ce tuto nous avons pu aborder la récursivité, un concept fort de la programmation qui peut être simulé (même si c'est un peu maladroit) dans des events communs.
Cela ne vous servira pas dans toutes les situations mais je pense qu'il existe de nombreux cas comme le calcul du modulo qui peuvent se révéler intéressants, ne serait-ce que pour le plaisir de programmer autrement !

Aucun commentaire n'a été posté pour le moment.

Suite à de nombreux abus, le post en invités a été désactivé. Veuillez vous inscrire si vous souhaitez participer à la conversation.

Haut de page

Merci de ne pas reproduire le contenu de ce site sans autorisation.
Contacter l'équipe

Plan du site:

Activité: Accueil | News | Forum | Flash-news | Chat | Commentaires | Galerie | Screen de la semaine | Sorties | Articles perso | Livre d'or | Recherche
Jeux: Index jeux séparés | Top Classiques | Top Originaux | Les autres | RPG Maker 95 | RPG Maker 2000 | RPG Maker 2003 | RPG Maker XP | RPG Maker VX | RPG Maker VX Ace | RPG Maker MV | Autres | Jeux complets | Proposer
Rubriques: Le Wiki | Collection Oniro | Tutoriaux | Scripts | Guides | Gaming-Live | Tests | Making-of | Interviews | Articles perso | OST | L'Annuaire | Divers | Palmarès
Hébergés: Aëdemphia | Fighting Robots Quest | Forstale | Geex | Inexistence | La Légende d'Ibabou | Lije | LoveMaster | Sarcia | Super Mario RPG - Lost Souls
Ressources: Jeux | Programmes | Packs de ressources | Midis | Eléments séparés | Sprites
RPG Maker 2000/2003: Chipsets | Charsets | Panoramas | Backdrops | Facesets | Battle anims | Battle charsets | Monstres | Systems | Templates
RPG Maker XP: Tilesets | Autotiles | Characters | Battlers | Window skins | Icônes | Transitions | Fogs | Templates
RPG Maker VX: Tilesets | Charsets | Facesets | Systèmes
RPG Maker MV: Tilesets | Characters | Faces | Systèmes | Title | Battlebacks | Animations | SV/Ennemis