|
Trouver une ressource
Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum. Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !
RÉCURSIVITÉ : FONCTION DE CALCUL DE PUISSANCE ET FACTORIELLE
Information sur le tutorial
Description
Cours sur les fonctions récursives, basé sur l'exemple d'une fonction qui calcul la puissance p d'un nombre n, et d'une fonction calculant la factorielle d'un nombre n.
Tutorial
Introduction Les fonctions récursives peuvent se révéler très utiles pour des tâches réitératives. On peut les utiliser par exemple pour le calcul de puissance, de factorielles. Plus utile encore, on peut les utiliser pour créer l'arborescence entière d'un répertoire contenant d'autres répertoires, et des fichiers.
En quoi cela conciste ? Ce sont des fonctions qui dans leur définition se rappellent elle-même. Dis comme ça, ça peut paraître assez peu évident, voici donc l'explication par l'exemple.
Fonction de calcul de puissance Prenons deux entiers naturels : n et p. petit rappel : n à la puissance p, noté "np" ou "n^p", c'est en fait p fois le produit de n par lui-même, soit n1 * n2 * n3 * n4 * ........ * np (les nombres en indice sont les étapes) Par exemple, 35 = 3 * 3 * 3 * 3 * 3 = 243 ( c'est à dire le produit de 3 par 3, 5 fois). De plus : np=np-1 * n Avec le même exemple : 35 = 34 * 3 Voici ce que donne la fonction : function my_pow ( $n ) { if ( $p == 0 ) { return ( 1 ); } return ( my_pow ( $n , $p -1 ) * $n ); } Et voici l'explication : On voit qu'ici, dans sa définition même, on utilise la fonction my_pow(), qui prend comme argument le même nombre n, mais la puissance p diminuée de 1, et cela s'arrête quand cet argument p sera inférieur ou égal à 0. Pour comprendre comment cela fonctionne, il faut enfaite partir par la fin, c'est à dire quand p vaut 0. p vaut 0, la fonction retourne 1. Comme on prend l'algorithme dans l'autre sens, il faut maintenant augmenter p de 1. p vaut donc maintenant 1, la fonction retourne le produit de 1 par le nombre n. -> On peut noter ici que si l'argument initial p valait 1, on se serait arrêter ici, et dans ce sens et on aurait bien n1. Le rèste continue ainsi de suite jusqu'à arriver à p. Voici maintenant l'explication dans le vrai sens avec l'expression de la fonction, pour np :
Posons $p = 4; my_pow ( $n , $p -1 ) = my_pow ( $n , $p -2 ) * $n OR, my_pow ( $n , $p -2 ) = my_pow ( $n , $p -3 ) * $n OR, my_pow ( $n , $p -3 ) = my_pow ( $n , $p -4 ) * $n Comme $p = 4, on vérifie maintenant la condition du if ( ( $p = $p -4 ) == 0 ) . La fonction retourne 1 : my_pow ( $n , $p -4 ) = 1 Revenons maintenant en arrière : my_pow ( $n , $p -3 ) = 1 * $n DONC, my_pow ( $n , $p -2 ) = ( 1 * $n ) * $n Donc, my_pow ( $n , $p -1 ) = [ ( 1 * $n ) * $n ] * $n = $n * $n * $n La fonction retourne donc : my_pow ( $n , $p -1 ) * $n = $n * $n * $n * $n = $n 4 Si $p avait été plus grand, vous devez maintenant comprendre qu'on serait aller plus loin ;) Si vous essayez cet exemple, n'oubliez pas d'afficher le résultat avec la fonction echo, par exemple : echo my_pow ( 3, 5 ); Fonction de calcul de factoriel Prenons un entier naturel : n petit rappel : Factorielle n, noté n ! , est le produit de tous les entiers de 1 jusqu'à n, soit 1 * 2 * 3 * 4 * ........ * n Par exemple : 5 ! = 1 * 2 * 3 * 4 * 5 = 120 De plus : n ! = (n-1) ! * n Avec le même exemple : 5 ! = 4 ! * 5 function my_fact ( $n ) { if ( $n == 1 ) { return ( 1 ); } return ( my_fact ( $n - 1 ) * $n ); }
Explication :
Posons $n = 5;
my_fact ( $n - 1 ) = my_fact ( $n - 2 ) * $n OR, my_fact ( $n - 2 ) = my_fact ( $n - 3 ) * $n
OR, my_fact ( $n - 3 ) = my_fact ( $n - 4 ) * $n Comme $n = 5, on vérifie maintenant la condition du if ( ( $n = $n -4 ) == 1 ) . La fonction retourne 1 : my_fact ( $n , $p -4 ) = 1 Revenons maintenant en arrière : my_fact ( $n , $p -3 ) = 1 * $n [Ici $n vaut 2] = 1 * 2 DONC, my_fact ( $n , $p -2 ) = ( 1 * 2 ) * $n [Ici $n vaut 2] = 1 * 2 * 3 Donc, my_fact( $n, $p-1 )= (1* 2 * 3)*$n [Ici $n vaut 2] =1*2 * 3 * 4La fonction retourne donc : my_pow( $n, $p-1 ) * $n=(1*2 * 3 * 4)*$n [Ici $n vaut 5] =1*2 * 3 * 4 * 5 = 5!
Encore une fois, si vous essayez cet exemple, n'oubliez pas d'afficher le résultat avec la fonction echo, par exemple :echomy_fact( 5 );
J'espère vous avoir éclairé sur ces fonctions très utiles ! Bonne prog ! ;-)
Historique
- 06 janvier 2007 15:52:00 :
- mise en page
- 06 janvier 2007 15:53:13 :
- encore mise en page ^^
Commentaires
|
Comparez les prix Nouvelle version
|