3 réponses
Bonjour,
En fait la fonction s'ecrit comme ça:
(defun fact (n) ; définition de la fonction
(if (= n 1) ; si n = 1
1 ; alors retourne 1
(* n (fact (- n 1))) ; sinon retourner n*(fact(n-))
)
)
Fonction récursive qui s'appelle elle même jusqu'à n=1
Les résultats intermédiaires sont retournés à la focntion appelante, le resultat final est retourné par la fonction du premier appel
Pour n=3
(fact (3)) -> 3*(3-1)*((3-1)-1)=3*2*1=6
Le resultat retourné est généralement stocké dans une variable
par exemple
(setq n fact(3))
(princ n)
En fait la fonction s'ecrit comme ça:
(defun fact (n) ; définition de la fonction
(if (= n 1) ; si n = 1
1 ; alors retourne 1
(* n (fact (- n 1))) ; sinon retourner n*(fact(n-))
)
)
Fonction récursive qui s'appelle elle même jusqu'à n=1
Les résultats intermédiaires sont retournés à la focntion appelante, le resultat final est retourné par la fonction du premier appel
Pour n=3
(fact (3)) -> 3*(3-1)*((3-1)-1)=3*2*1=6
Le resultat retourné est généralement stocké dans une variable
par exemple
(setq n fact(3))
(princ n)
merci ,
je ne comprend pas la parti (* n (fact (- n 1))) que veux dire fact a cette position et comment cette expression se boucle elle même sans faire une boucle ?
je ne comprend pas la parti (* n (fact (- n 1))) que veux dire fact a cette position et comment cette expression se boucle elle même sans faire une boucle ?
C'est facile à comprendre
1) premier appel
(setq X fact(3)) ; par exemple
la fonction fact() reçoit comme argument n=3
n different de 1 alors
n=n*fact(n-1) soit n=3*fact(2)
appelons A la valeur fac(2) attendue
2) au deuxieme appel la fonction fact() reçoit comme argument n=2
n different de 1 alors
n=n*fact(n-1) soit n=2*fact(1)
appelons B la valeur fact(1) attendue
3)au troisième appel la fonction fact() reçoit comme argument n=1
n=1 alors retourne 1 a la fonction appelante
donc B=1
on remplace B par sa valeur dans le 2)
n=2*B soit n=2*1=2 et retourne 2 à la fonction appelante
donc A=2
on remplace A par sa valeur dans le 1)
n=3*A soit n=3*2=6 et retourne 6 à la fonction appelante
donc X=6
Voila.
Techniquement, ces opérations se passent dans une zone mémoire appelée la Pile (Stack). Cette zone est gérée par un registre du microprocesseur qui s'appelle Stack Pointer (SP). La pile à une dimension prédéfinie non extensible pour chaque programme. Quand une fonction récurrente comme celle décrite s'appelle elle-même un grand nombre de fois, on finit par avoir une erreur "Stack overflow" (dépassement de la pile). Cette erreur est irrécupérable et plante le programme.
J'espère que c'est un peu plus clair dans ta tête. J'avoue que c'est pas évident, et à moins d'y être obligé comme en langage assembleur, mois vaut d'en tenir aux principes.
A+.
1) premier appel
(setq X fact(3)) ; par exemple
la fonction fact() reçoit comme argument n=3
n different de 1 alors
n=n*fact(n-1) soit n=3*fact(2)
appelons A la valeur fac(2) attendue
2) au deuxieme appel la fonction fact() reçoit comme argument n=2
n different de 1 alors
n=n*fact(n-1) soit n=2*fact(1)
appelons B la valeur fact(1) attendue
3)au troisième appel la fonction fact() reçoit comme argument n=1
n=1 alors retourne 1 a la fonction appelante
donc B=1
on remplace B par sa valeur dans le 2)
n=2*B soit n=2*1=2 et retourne 2 à la fonction appelante
donc A=2
on remplace A par sa valeur dans le 1)
n=3*A soit n=3*2=6 et retourne 6 à la fonction appelante
donc X=6
Voila.
Techniquement, ces opérations se passent dans une zone mémoire appelée la Pile (Stack). Cette zone est gérée par un registre du microprocesseur qui s'appelle Stack Pointer (SP). La pile à une dimension prédéfinie non extensible pour chaque programme. Quand une fonction récurrente comme celle décrite s'appelle elle-même un grand nombre de fois, on finit par avoir une erreur "Stack overflow" (dépassement de la pile). Cette erreur est irrécupérable et plante le programme.
J'espère que c'est un peu plus clair dans ta tête. J'avoue que c'est pas évident, et à moins d'y être obligé comme en langage assembleur, mois vaut d'en tenir aux principes.
A+.
