Récursivité : fonction de calcul de puissance et factorielle

Décembre 2017


Récursivité : fonction de calcul de puissance et factorielle


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 consiste ?
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, $p)

{

    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, en fait 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êté ici, et dans ce sens et on aurait bien n1.
Le reste 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 = $n4

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);

}


Explications :

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 * 4


La fonction retourne donc :
my_fact($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 :
echo my_fact(5);


J'espère vous avoir éclairé sur ces fonctions très utiles !
Bonne prog ! ;-)

A voir également

Publié par bthivent.
Ce document intitulé «  Récursivité : fonction de calcul de puissance et factorielle  » issu de CodeS-SourceS (codes-sources.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.
Ajouter un commentaire

Commentaires

Commenter la réponse de coucou747
Crée un flux rss à partir d'un formulaire
Les sessions php, comment ça marche ?