Récursivité : fonction de calcul de puissance et factorielle
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 ! ;-)
- Fonction puissance recursive
- Puissance en c - Meilleures réponses
- Fonction puissance algorithme - Meilleures réponses
- Recursivite java - Forum Java
- Recursivite python - Forum Python
- Recursivité ✓ - Forum C# / .NET
- Récursivité ??? - Forum Delphi / Pascal
- Python récursivité - Forum Python