Recursivité terminal sur caml

[jujudu597]

Bonjour,

J'essaie de comprendre le principe de la récursivité terminal mais cela me semble difficile.

J'ai vu que la fonction factorielle s'écrivait ainsi

let factorielle n =
let rec factorielle_aux n acc =
if n = 0 then
acc
else
factorielle_aux (n-1) (n*acc) in
factorielle_aux n 1

Cependant, je comprend pas le principe du acc.
Pourquoi quand n = 0 il fais 1?

D'avance merci :)

[kelthuzad]

Salut

Pourquoi quand n = 0 il fais 1?

Si c'est juste ça ta question, c'est par convention. factorielle 0 n'a pas de sens, on décide que 0! = 1, au cas où la fonction recevrait 0 on gère ce cas et on renvoie la valeur 1 comme défini en math.

[joel76]

Au premier abord, en récursif, la fonction factoriel s'écrit

Code: Tout sélectionner

int fact(n)
début
   si n = 0 alors
      1
   sinon
      n * fact(n - 1)
fin

Que constate-t-ton ?
Que pour calculer fact(n) , on calcule d'abord fact(n-1) puis on multiplie le résultat obtenu par n.
Les appels successifs s'empilent pour pouvoir exécuter le code, car à la fin d'un appel il faut faire une multiplication.

Avec la version avec accumulateur, plus besoin d'empiler les appels :

Code: Tout sélectionner

int fact(n)
   fact_acc(n, 1)
   

int fact_acc(n, acc)
   si n = 0 alors
      acc
   sinon
      fact_acc(n-1, n * acc)


Lorsque n = 0 on renvoie directement la valeur de l'accumulateur, plus de calculs pour le retour.
exemple

fact(3) ==> fact_acc(3, 1)

fact_acc(3, 1)
n 0 donc on renvoie fact_acc(3-1, 3 * 1) soit fact_acc(2,3)

fact_acc(2, 3)
n 0 donc on renvoie fact_acc(2-1, 2 * 3) soit fact_acc(1,6)

fact_acc(1, 6)
n 0 donc on renvoie fact_acc(1-1, 1 * 6) soit fact_acc(0,6)

fact_acc(0, 6)
n = 0 donc on renvoie 6

Quel est l'intérêt ? le compilo détecte cette récursion "terminale" et donc transforme le calcul en traitement itératif.

[jujudu597]

Merci bcp a vous pour vos réponses.

je ne comprend toujours pas bien pourquoi acc vaut 1 quand n = 0.
Je comprend bien que 0! = 1 mais acc n'a aucune valeur donc pourquoi 1?

Sinon je comprend mieux le principe! Mais j'ai un peu de mal avec le
"else
factorielle_aux (n-1) (n*acc) in
factorielle_aux n 1"

Pourquoi a-ton besoin d'un "in"?

Pourquoi ne peut on pas écrire
let factorielle n =
let rec factorielle_aux n acc =
if n = 0 then
acc
else
factorielle_aux (n-1) (n*acc)