Night.png);">
Apprendre


Vous êtes
nouveau sur
Oniromancie?

Visite guidée
du site


Découvrir
RPG Maker

RM 95
RM 2000/2003
RM XP
RM VX/VX Ace
RM MV/MZ

Apprendre
RPG Maker

Tutoriels
Guides
Making-of

Dans le
Forum

Section Entraide

Sorties: Star Trek: Glorious Wolf - (...) / Sorties: Dread Mac Farlane - episode 3 / News: Plein d'images cools créées par (...) / Sorties: Star Trek: Glorious Wolf - (...) / Jeux: Final Fantasy 2.0 / Chat

Bienvenue
visiteur !




publicité RPG Maker!

Statistiques

Liste des
membres


Contact

Mentions légales

266 connectés actuellement

29187754 visiteurs
depuis l'ouverture

2805 visiteurs
aujourd'hui



Barre de séparation

Partenaires

Indiexpo

Akademiya RPG Maker

Blog Alioune Fall

Fairy Tail Constellations

RPG Maker - La Communauté

ConsoleFun

Level Up!

Tous nos partenaires

Devenir
partenaire



EMG 07 : La récursivité

Où on s'intéresse à la récursivité.

Ecrit par François Berhn le 22/06/2016


❤ 0

EMG 7 : La récursivité










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 exécute le seconde qui exécute 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 passerait :
- 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 - Mentions légales

Plan du site

Communauté: Accueil | Forum | Chat | Commentaires | News | Flash-news | Screen de la semaine | Sorties | Tests | Gaming-Live | Interviews | Galerie | OST | Blogs | Recherche
Apprendre: Visite guidée | RPG Maker 95 | RPG Maker 2003 | RPG Maker XP | RPG Maker VX | RPG Maker MV | Tutoriels | Guides | Making-of
Télécharger: Programmes | Scripts/Plugins | Ressources graphiques / sonores | Packs de ressources | Midis | Eléments séparés | Sprites
Jeux: Au hasard | Notre sélection | Sélection des membres | Tous les jeux | Jeux complets | Le cimetière | RPG Maker 95 | RPG Maker 2000 | RPG Maker 2003 | RPG Maker XP | RPG Maker VX | RPG Maker VX Ace | RPG Maker MV | Autres | Proposer
Ressources RPG Maker 2000/2003: Chipsets | Charsets | Panoramas | Backdrops | Facesets | Battle anims | Battle charsets | Monstres | Systems | Templates
Ressources RPG Maker XP: Tilesets | Autotiles | Characters | Battlers | Window skins | Icônes | Transitions | Fogs | Templates
Ressources RPG Maker VX: Tilesets | Charsets | Facesets | Systèmes
Ressources RPG Maker MV: Tilesets | Characters | Faces | Systèmes | Title | Battlebacks | Animations | SV/Ennemis
Archives: Palmarès | L'Annuaire | Livre d'or | Le Wiki | Divers