(* Corrige d'Introduction à la programmation   *)
(* Exercices sur la récursivité                *)


(* Élever un nombre flottant à une puissance entière *)
(*-------------------------------------------------- *)

(* Écrire en Caml une fonction qui, à partir d'un entier positif
  n et d'un flottant x, renvoie la valeur de x^n. Avant d'écrire
  cette fonction, élaborer un algorithme qui calcule cette valeur de
  façon récursive.*)

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

(* Ecrire votre fonction en utilisant le filtrage de $n$.*)

let rec puissance x = function
  0 -> 1
 |n -> x * puissance x (n-1);;



(* La somme des n premiers entiers *)
(*-------------------------------- *)

(* On peut calculer la somme des n premier entiers au moins de deux
  manières différentes. Une de ces deux manières correspond à un
  algorithme récursif. Implémenter cet algorithme par deux fonctions
  Caml dont l'une est récursive et qui, étant donné un entier positif n, 
  renvoient la somme des n premiers entiers.*)

let SommeNPremiersEntiers n = n * (n-1) / 2;;
 
let rec SommeNPremiersEntiers n = if(n=0) then 0 else 
       n + SommeNPremiersEntiers(n-1);;



(* La division entière *)
(*-------------------- *)

(* Nous cherchons à réaliser une fonction qui, à partir de deux
  entiers positifs a et b, renvoie le quotient de la division de
  a par b. On cherche à réaliser cela sans utiliser l'opérateur de
  division de Caml.  Dans un premier temps, écrire l'algorithme
  de cette division sous la forme d'une récursion. *)

 let rec div a b = 
     if a < b or a=0 then 0
     else 1 + div (a-b) b;;
 

(* Meme question, mais pour le reste de la division de a par b. *)

 let rec reste a b =
     if b=0 then (-1)
     else if a=0 then 0
     else if a < b then a
          else reste (a-b) b;;
 
(* REMARQUE : j'ai rajouté un cas pour éviter
  un bouclage sur la division par 0. *)



(* Multiplication par un entier p *)
(*-------------------------------- *)

(* Écrire une fonction qui à partir de deux entiers positifs 
  n et p calcule le produit n * p par une suite d'additions. *)

let rec mult a p =
    if p = 1 then a
    else a + mult a (p-1);;

let rec mult a p =
    if p = 0 or a = 0 then 0
    else if p = 1 then a
    else a + mult a (p-1);;

(* Est-ce que la fonction peut etre utilisée pour deux entiers négatifs ? *)
(* Réponse : non puisqu'en enlevant 1 à un nombre négatif p, on n'arrivera *)
(* jamais à 0 *)

(* Est-ce qu'elle peut etre utilisée avec un entier positif et un entier négatif ?*)
(* Oui il suffit que p soit positif et tout marche *)

(* Est-ce que l'algorithme peut etre généralisé pour la multiplication entre *)
(* flottants, ou entre un entier et un flottant ?                            *)
(* entier et flottant oui, flottant et flottant non *)



(* L'algorithme d'\emph{Euclide} pour le calcul du PGCD *)
(*----------------------------------------------------- *)

let rec pgcd a b = 
    if a = b then a 
    else if a < b then pgcd a (b-a) 
         else pgcd (a-b) b;;

let rec pgcd a b =
    if (a = b) or (b=0) then a
    else if (a=0) then b
    else if a < b then pgcd a (b-a)
         else pgcd (a-b) b;;


(* Le calcul de cos(nx) et sin(nx) *)
(*-------------------------------- *)

let premier (x,y) = x;;
let second  (x,y) = y;;

let rec CosSinAux cosx sinx n = 
match n with 0 -> (1.,0.) 
           | n -> let prec=CosSinAux cosx sinx (n-1) in 
		  let cos_nmoins1_x = premier prec and 
		      sin_nmoins1_x = second  prec in 
		(cos_nmoins1_x *. cosx -. sin_nmoins1_x *. sinx, 
		 sin_nmoins1_x *. cosx +. cos_nmoins1_x *. sinx);;

let CosSin x n = CosSinAux (cos x) (sin x) n;;


(* Renverser un nombre quelconque *)
(*------------------------------- *)

let rec OrdreDeGrandeur n =
    if n < 10 then 1
    else 10 * OrdreDeGrandeur (n/10);;

let rec renverser n = 
    if n < 10 then n
    else ((n mod 10) * OrdreDeGrandeur n) + renverser (n/10);;


(* Un nombre palindrome *)
(*--------------------- *)

let rec OrdreDeGrandeur n =
    if n < 10 then 1
    else 10 * OrdreDeGrandeur (n/10);;

let PoidsFort n = n/(OrdreDeGrandeur n);;

let PoidsFaible n = n mod 10;;

let Trognon n = (n mod (OrdreDeGrandeur n) - (PoidsFaible n))/10;;

let rec Palindrome n =
    if n < 10 then true else
    (PoidsFort n = PoidsFaible n) & Palindrome(Trognon n);;


(* La suite factorielle *) 
(*--------------------- *)

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


(* Les combinaisons Cnp *)
(*--------------------- *)

let rec combinaison n p =
    if n < p then 0
    else if p=0 then 1
    else (fact n) / ((fact p) * (fact (n-p)));;

(* En calculant C_14^7, on calcule trois fois le produit 7 x 6 x 5 x 4 x 3 x 2 *)

(* Exprimer C_n^p en fonction de C_{n-1}^{p-1} (sans faire intervenir C_{n-1}^p) *)

(* p C_n^p = n * C_{n-1}^{p-1} *)

(* En déduire une fonction capable de calculer C_n^p a partir de p et de n. *)

let rec combinaison n p = 
    if p=0 then 1
    else n / p * combinaison (n-1) (p-1);;

(* Essayer cette fonction pour calculer C_4^3 : 
est-ce qu'on obtient la valeur attendue ? *)

(* combinaison 4 3;; *)
(* - : int = 2       *)
(* alors que chacun sait que C_4^3 vaut 4.  *)

(* ERREUR : cette version ne marche pas bien car pour n/p il tronque *)
(*  (division entiere)  => nouvelle version en utilisant factorielle : *)


(* Enfin on essaie d'écrire cette fonction grâce au triangle de Pascal  *)

let rec combinaison n p = 
    if (p=0 or n=p) then 1
    else combinaison (n-1) (p-1) + combinaison (n-1) p ;;

let rec combinaison n p = 
    if n < p then 0
    else if (p=0 or n=p) then 1
    else combinaison (n-1) (p-1) + combinaison (n-1) p ;;


(* La suite de Fibbonacci *)
(*----------------------- *)

let rec fibbo n =
    if n = 0 then 1
    else if n = 1 then 1
    else fibbo (n-1) + fibbo (n-2);;

let rec fibbo = function 0 -> 1
                       | 1 -> 1
                       | n -> fibbo(n-1) + fibbo(n-2);;

(* Pour la fonction qui calcule la suite de Fibbonacci, 
combien de fois la fonction Fibbonacci est-elle appelée sur
les entiers N-1, N-2, ... N-5, lors du calcul de la valeur 
de la fonction pour un entier N ? *)

(* En fait la fonction est appelée 
 1  fois pour $N-1$, 
 2  fois pour $N-2$, 
 3  fois pour $N-3$, 
 5  fois pour $N-4$, 
 8  fois pour $N-5$, 
 13 fois pour $N-6$, 
 etc
 c'est la suite de \emph{Fibbonacci} elle-m\^eme. *)

(* V_{n+1} = (u_{n+1}, u_{n+2}) = 
 (second(V_n), premier(V_n) + second(V_n)) *)

let premier (x,y) = x;;
let second  (x,y) = y;;

let rec FibboAux n =
    if n = 0 then (1,1)
    else if n = 1 then (1,2)
    else let vn = FibboAux(n-1) in (second vn, premier vn + second vn);;
  
(* En déduire une fonction qui calcule la suite de 
  Fibbonacci en ne calculant chacun des termes de la suite
  qu'une seule fois. *)

let fibbo n = premier(FibboAux n);;