[Tuto] Les fonctions récursives
Posté : ven. 18 juin 2010 01:11
1 - Introduction et exemples
2 - Les vecteurs et diviser pour mieux résoudre
3 - Le tri rapide (Quicksort)
4 - Le Backtracking
Débat des membres
"En informatique et en mathématiques, le terme fonction récursive désigne une classe de fonctions calculables, autrement dit de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique."
Voici un premier exemple concret facile :
Vous verrez également qu'on peut très vite se triturer le cerveau, mais mon Dieu, que c'est magnifique :
Voici comment ça marche : Dans la fonction existe une condition de sortie, c'est If $n=0 . En clair on décrémente n jusqu'à ce que cette variable vaille 0. Donc d'abord, $n vaut 5 et res 5*FonctionFactorielle(4) etc. Ce raisonnement équivaut à remplacer :
$res = $n*FonctionFactorielle($n-1) par
$res = $n*FonctionFactorielle(4)*FonctionFactorielle(3)*FonctionFactorielle(2)*FonctionFactorielle(1)*FonctionFactorielle(0) soit 5*4*3*2*1*1.
N'hésitez pas à regarder l'image en attaché si vous avez encore quelques problèmes de compréhension.
2 - Les vecteurs et diviser pour mieux résoudre
3 - Le tri rapide (Quicksort)
4 - Le Backtracking
Débat des membres
"En informatique et en mathématiques, le terme fonction récursive désigne une classe de fonctions calculables, autrement dit de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique."
Wikipedia.org
En clair, la récursivité c'est de la récurrence. Dans une fonction, on rappelle cette même fonction et les variables varient dans les paramètres. Le but est, entre-autres, d'éviter les boucles.Voici un premier exemple concret facile :
Code : Tout sélectionner
Const $MAX = 10
FonctionRecursive(0)
Func FonctionRecursive($res)
If $res <= $MAX Then
msgbox(0,"Nombre", $res)
FonctionRecursive($res+1)
Endif
EndFunc
Code : Tout sélectionner
$resultat = FonctionFactorielle(5)
msgbox(0,"",$resultat) ; retourne 120 : 5*4*3*2*1*1
Func FonctionFactorielle($n)
local $res
If $n=0 Then ; la factorielle de 0 est 1
; condition de sortie
$res = 1
Else
$res = $n*FonctionFactorielle($n-1)
Endif
return $res
EndFunc
$res = $n*FonctionFactorielle($n-1) par
$res = $n*FonctionFactorielle(4)*FonctionFactorielle(3)*FonctionFactorielle(2)*FonctionFactorielle(1)*FonctionFactorielle(0) soit 5*4*3*2*1*1.
N'hésitez pas à regarder l'image en attaché si vous avez encore quelques problèmes de compréhension.