Accueil > > > RÉCURSIVITÉ : FONCTION DE CALCUL DE PUISSANCE ET FACTORIELLE
RÉCURSIVITÉ : FONCTION DE CALCUL DE PUISSANCE ET FACTORIELLE
Information sur le tutoriel
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
|
Derniers Blogs
GESTION D'EXCEPTION AVEC LES TASKSGESTION D'EXCEPTION AVEC LES TASKS par richardc
Nous avons vu dans un précédent article comment utiliser Task pour effectuer des opérations dans un autre thread.
Malheureusement, comme tout le monde n'est pas parfait, il se peut que cette exécution se passe mal et qu'une exception se produise.
La...
Cliquez pour lire la suite de l'article par richardc DéMARRONS AVEC LES TASKSDéMARRONS AVEC LES TASKS par richardc
Que vous le vouliez ou non, le développement multi-tâche est maintenant une obligation pour toute nouvelle application. Il est donc vital d'en comprendre les mécanismes et de s'y mettre le plus tôt possible.
En attendant le .NET Framework 4.5 avec le...
Cliquez pour lire la suite de l'article par richardc SLIDE & DéMO TECHDAYS 2012 - FAST & FURIOUS XAML APPSSLIDE & DéMO TECHDAYS 2012 - FAST & FURIOUS XAML APPS par Vko
Retrouvez les slides et les démo de ma session Fast & Furious XAML Apps. A ceux qui se posent la question : "est-ce que le code de la DataGrid est disponible?", je vous répondrais "pas encore". Je vais mettre en place un projet codeplex pour part...
Cliquez pour lire la suite de l'article par Vko XNA IS DEAD!XNA IS DEAD! par richardc
Depuis la semaine dernière (et grâce aux TechDays 2012), je me penche activement sur la nouvelle version de Windows, aka Windows 8. Vous me direz, il était temps puisque la première preview date de Septembre dernier.
OK. Remarquez, on n'en est qu'aux...
Cliquez pour lire la suite de l'article par richardc TECHDAYS PARIS 2012 : WINDOWS SERVER "8" QUOI DE 9 !TECHDAYS PARIS 2012 : WINDOWS SERVER "8" QUOI DE 9 ! par ROMELARD Fabrice
Speakers: Fabrice Meillon et Stanislas Quastana Cette session est basée entièrement sur celle donnée lors de la BUILD cet hiver. Il n'y a pas d'ajout d'information en rapport avec cet évènement passé. Windows 8 Server sera intégralem...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice
Logiciels
DocTranslate (V3.1.0.0)DOCTRANSLATE (V3.1.0.0)DocTranslate est un traducteur de document Microsoft Word, PowerPoint et Excel. Il permet d'autom... Cliquez pour télécharger DocTranslate Tribler (2012)TRIBLER (2012)Tribler est un client pair à pair (P2P/Peer-to-Peer) open source avec la capacité de regarder des... Cliquez pour télécharger Tribler OneSwarm (2012)ONESWARM (2012)Le peer-to-peer qui protège votre vie privée, c'est OneSwarm.
Ce logiciel de peer-to-peer crypté... Cliquez pour télécharger OneSwarm PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO (V8.4)PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO (V8.4)PONAMEDIA TV DEVIENS HELLLOOO FLASH
LA TV SUR VOTRE ORDINATEUR.
Toute une plateforme Multi... Cliquez pour télécharger PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO Academy System (17.2.1.0)ACADEMY SYSTEM (17.2.1.0)Logiciel de gestion des établissements.
- élèves/étudiants (inscription, dossier, absence...)
-... Cliquez pour télécharger Academy System
|