Bonsoir. J'ai commencé à apprendre l'Ocaml (par curiosité) cet après midi.
J'ai essayé de refaire la factorielle de Bluestorm dans son tuto sur la récursivité.

Et j'ai un souci à l'exécution. Quand je tape :

> fact(5);; (* j'obtiens 120, normal *)
> fact(18);; (* j'obtiens -8900... *)

j'ai ce problème avec ces deux fonctions:

let rec fact x=
    if x = 0 then 1
    else x * fact (x-1);;

let rec fact acc x=
    if x = 0 then acc
    else fact (n*acc) (n-1);;

(* j'utilise la deuxième en faisant fact 1 18 *)

Je suis (hélas) sous Windows...

Note: y-a t-il des recommandations particulières concernant la syntaxe ?

Merci d'avance.

Le problème vient du fait qu'un entier ne peut stocker qu'une valeur de -2³¹ à 2³¹ (63 en 64 bits). Il y a donc un phénomène d'overflow, qui fait que ton nombre dépasse la limite et devient négatif (c'est du à la représentation des entiers signés en binaire).

Il faut donc utiliser un module fait pour ça. Pour 18!, Int64 suffit probablement, Sinon, Big_int si mes souvenirs sont bons.

Le comportement n'est pas anormal. Le nombre entier que tu manipules est "trop grand" (factorielle 18 c'est un nombre énorme, environ 6.10^15), et il provoque ce qu'on appelle un "dépassement de capacité" : il est trop gros pour être représenté par un entier en taille machine, et cela provoque un dépassement de capacité.

C'est un problème qui se rencontre dans tous les langages qui ont conservé une gestion "simple" des types numériques (C, C++ et je pense Java y compris). D'autres langages ont choisi de passer, en cas de risque de dépassement, de basculer vers une représentation différente des entiers, de manière invisible pour le programmeur. C'est aussi un bon choix mais ça a un coût en performance (et certaines applications ne peuvent pas se le permettre, d'où le choix des concepteurs OCaml de ne pas le faire pour les entiers par défaut).

Les trois solutions sont :

- utiliser une machine où les entiers par défaut sont assez grands pour contenir la valeur. Sur une version compilée en 64 bits, ça devrait tenir. Mais c'est une solution temporaire parce que factorielle(28) dépassera à nouveau.

- utiliser un type à plus grande capacité : le calcul sur les float est plus imprécis mais le type est plus grand, donc il peut contenir plus de valeurs : let rec fac n = if n = 0 then 1. else float n *. fac (n - 1);;
Même limitations que pour les entiers par défauts : au bout d'un moment, ça dépasse forcément.

- utiliser un type d'entiers de taille arbitraire. En OCaml ils sont contenus dans la bibliothèque Num. Ça marche mais c'est un peu plus lent (forcément) et un peu plus chiant à utiliser (il faut indiquer au compilateur qu'on veut la bibliothèque, etc.)

- passer sur ce problème qui n'est en général pas important (tu as vraiment besoin de la factorielle de 18 ?), et continuer avec autre chose. Choix conseillé.

Cependant, même en cas de dépassement de capacité, les résultats calculés par OCaml te semblent faux (en fait ils sont justes, mais modulo un certain nombre) mais il peut poursuivre les calculs. Tu peux donc quand même vérifier la différence entre tail-récursivité et fonction "normale" en demandant de très grandes valeur (selon la manière dont tu utilises OCaml, ça peut aller de 5000 à plusieurs centaines de milliers) : au bout d'un moment, tu auras une erreur avec la version "normale", due à la surcharge de la pile.

Ah d'accord...
J'ai testé cette fonction en Python la première fois... forcément^^
Donc je vais oublier 18!

Merci beaucoup !