RÉCURSIVITÉ : FONCTION DE CALCUL DE PUISSANCE ET FACTORIELLE

---

Commentaire sur cette source (7)
Ajouter un commentaire et/ou une note

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.

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é "n^p" ou "n^p", c'est en fait p fois le produit de n par lui-même, soit n₁ * n₂ * n₃ * n₄ * ........ * n_p  (les nombres en indice sont les étapes)
Par exemple, 3⁵ = 3 * 3 * 3 * 3 * 3 = 243  ( c'est à dire le produit de 3 par 3, 5 fois).
De plus : n^p=n^p-1 * n
Avec le même exemple : 3⁵ = 3⁴ * 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 n¹.
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 n^p :

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 ⁴

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

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

06 janvier 2007 15:52:00 :

mise en page

06 janvier 2007 15:53:13 :

encore mise en page ^^