Leçons PHP - leçon 9 - Récursion
Dans la leçon précédente, nous avons examiné l'utilisation des fonctions en PHP. Maintenant, allons un peu plus en profondeur dans leur utilisation. Avant cette leçon, nous avons étudié des fonctions de ce type :
<?php function maFonction(){ // définition de la fonction } $x = maFonction(); // appel de la fonction ?>
Mais que se passe-t-il si l'on appelle une fonction directement dans le corps de cette fonction ?
<?php function maFonction(){ $x = maFonction() ... return $x; } $y = maFonction();
Un tel appel d'une fonction à l'intérieur d'elle-même s'appelle la récursion. Cela paraît assez compliqué en théorie, mais en pratique c'est beaucoup plus simple.
Créons une fonction pour calculer la puissance d'un nombre. D'après le cours d'algèbre, vous vous souvenez sans doute que la n-ième puissance d'un nombre signifie que ce nombre est multiplié par lui-même n fois. En PHP, cela ressemblera à ceci :
<?php function maPuissance($x, $n){ if($n == 0){ return 1; } if($n < 0){ return maPuissance(1/$x, -$n); // -$n signifie changement du signe de négatif à positif } return $x * maPuissance($x, $n-1); // appel de la fonction à l'intérieur d'elle-même } $y = maPuissance(2, -4); // tout premier appel de la fonction print $y; ?>
Analysons maintenant cette fonction en détail. Commençons par le fait qu'après une instruction return, la fonction ne s'exécute plus et renvoie la valeur indiquée dans le return.
La première condition if($n == 0) - si notre exposant est égal à 0, alors la fonction renvoie 1. Cela est clair et simple : toute puissance 0 d'un nombre vaut 1. Ensuite, if($n < 0) - si nous donnons un exposant négatif, alors nous transformons l'exposant en positif, mais en inversant le nombre élevé à la puissance en fraction, ce qui est conforme à la définition des puissances, et que nous utilisons ici.
Enfin, la dernière partie s'exécute si l'exposant n'est ni 0 ni négatif, alors nous appelons la fonction en réduisant à chaque fois l'exposant de 1, tout en multipliant chaque fois notre nombre par $x.
Voyons chaque itération (répétition) de notre fonction :
1. Exposant -4, nombre 2.
Ici, la deuxième condition if sera exécutée, notre nombre devient fractionnaire, et l'exposant devient positif.
2. Exposant 4, nombre 0,5.
L'exposant est positif et différent de 0, donc nous passons le if et la ligne suivante est exécutée :
return $x * maPuissance($x, $n-1)
3. Exposant 3, nombre 0,25.
4. Exposant 2, nombre 0,125.
5. Exposant 1, nombre 0,0625.
Ici, la première condition if s'exécute, c'est-à-dire que 1 est renvoyé, ce 1 sera multiplié par les résultats précédents des fonctions et la récursion s'arrêtera.
Un autre exemple similaire est le calcul de la factorielle d'un nombre. La factorielle d'un nombre n est le produit de tous les nombres de 1 à n. Par exemple, pour le nombre 6, la factorielle est 6*5*4*3*2*1 = 720. Et comme vous l'avez probablement deviné, nous utiliserons la récursion.
<?php function maRecursion($x){ if($x == 1){ return $x; } return $x * maRecursion($x - 1); } $y = maRecursion(8); print $y; ?>
Cet exemple est encore plus simple que le premier, donc je vous laisse analyser vous-même les changements des paramètres pour la fonction maRecursion.