Cours 4 : Récursivité et exemples
Récursivité
On parle de récursivité quand un objet est auto-référent... c'est-à-dire qu'il participe à sa propre définition. On l'a déjà vu sur les types, comme pour 'a liste. En général, quand un type est récursif, les fonctions qui le manipulent le sont. D'où ce cours, plus focalisé sur les fonctions récursives. Une fonction récursive f contient f dans l'expression qui suit la flèche, soit let f = function x -> ...f...
Ce n'est pas...
Essayons:
let f = function x -> (f x) + 1;;
Essayons alors
let f = function x -> x*3;;
let f = function x -> (f x) + 1;;
f 5;;
Mais est-ce récursif ? Reprenons la première expression, mais en utilisant le mot-clé rec... et en utilisant un symbole libre, disons g.
let rec g = function x -> (g x) + 1;;
g 38;;
La fameuse factorielle
Réécrivons à la main ces deux versions: La version du mathématicien:
let rec fact1 = 
  function
      0          -> 1
    | n when n>0 -> n * (fact1 (n - 1))
    | _          -> failwith ("l'argument doit etre positif !");;

fact1 4;;
La version du bidouilleur:
let fact2 =
  function n ->
    let rec fact_iter = function   (0,res)          -> res
                                 | (m,res) when m>0 -> fact_iter (m-1, m*res)
				 | _                -> failwith ("l'argument doit etre positif !")
    in
      fact_iter (n,1);;

fact2 4;;
Alors ? Quelle est la meilleure ?
Concevoir ses propres fonctions
Une fonction est un service qu'on délègue sans se préoccuper de savoir comment ce service délégué est réalisé. La question est denc de savoir si, pour rendre un service souhaité à partir d'une donnée, il peut m'être utile de disposer de ce service... sur une donnée un peu différente. Si oui, il suffit de l'écrire.
Exemples
Accès aux éléments d'une liste
nb_elem [2;4;6;7;9];;
- : int = 5





let rec nb_elem = 
  function   []   -> 0
           | _::r -> 1+(nb_elem r);;    
val nb_elem : 'a list -> int = 





nieme ["toto";"titi";"tutu"] 2;;
- : string = "titi"





let rec nieme = 
  function l ->
  function n ->
    match (n,l) with
        (1,t::r)           -> t
      | (n,t::r) when n>1  -> nieme r (n-1)
      | (n,[])   when n>=0 -> failwith "La liste est trop petite"
      | _                  -> failwith "La position n'a pas de sens";;
      
Liste paires
let prenoms = ["David";"Peter";"Bruce";"Clark";"Matt"];;
let noms    = ["Banner";"Parker";"Waine";"Kent";"Murdock"];;
let super   = ["Hulk";"Spiderman";"Batman";"Superman";"Dardevil"];;

let identite         = apparie prenoms noms;;
let identite_secrete = apparie super   identite;;






let rec apparie = 
  function l1 ->
  function l2 ->
    match (l1,l2) with
        (  []  ,  []  ) -> []
      | (t1::r1,t2::r2) -> (t1,t2)::(apparie r1 r2)
      | (  _   ,  []  ) -> failwith "Premiere liste trop longue"
      | (  []  ,  _   ) -> failwith "Deuxieme liste trop longue";;





retrouve "Batman" identite_secrete;;
- : string * string = ("Bruce", "Waine")





let rec retrouve =
  function cle ->
  function
      []                                      -> failwith ("La cle n'est pas dans la liste")
    | (la_cle,la_valeur)::_ when la_cle = cle -> la_valeur
    | _::r                                    -> retrouve cle r;;
      
Calcul formel
Les formules sont des arbres.... d'où:
 
type formule =   Valeur    of float  
               | Inconnue  of string
               | Opp       of formule
               | Plus      of formule * formule
               | Fois      of formule * formule
               | Moins     of formule * formule
               | Sur       of formule * formule
               | Fonction  of string  * formule
               | DFonction of string  * string * formule;;

let f = Fois (Fonction ("f",Inconnue "x"), Plus (Valeur 1.0, Fonction ("tan", Sur (Inconnue "x", Inconnue "y"))));;
string_of_formule f;;
- : string = "(f(x)) * ((1.) + (tan((x) / (y))))"





let rec string_of_formule =
  function 
      Valeur x          -> string_of_float x
    | Inconnue x        -> x
    | Opp x             -> "-("^(string_of_formule x)^")"
    | Plus (a,b)        -> "("^(string_of_formule a)^") + ("^(string_of_formule b)^")"
    | Fois (a,b)        -> "("^(string_of_formule a)^") * ("^(string_of_formule b)^")"
    | Moins (a,b)       -> "("^(string_of_formule a)^") - ("^(string_of_formule b)^")"
    | Sur (a,b)         -> "("^(string_of_formule a)^") / ("^(string_of_formule b)^")"
    | Fonction (f,x)    -> f^"("^(string_of_formule x)^")"
    | DFonction (f,a,x) -> "d"^f^"/d"^a^"("^(string_of_formule x)^")";;
On va simplifier via deux fonctions, afin d'éviter des récurrences infinies... On fera une simplification non récursive et une récursive.
let rec simplifie =
  function f ->
  let simple = function 
      Opp (Opp x)                             -> x
    | Plus  (Valeur 0.0, x                  ) -> x
    | Plus  (x         , Valeur 0.0         ) -> x
    | Plus  (x         , Opp y              ) -> Moins (x, y)
    | Plus  (Opp x     , y                  ) -> Moins (y, x)
    | Moins (x         , Valeur 0.0         ) -> x
    | Moins (Valeur 0.0, x                  ) -> Opp x
    | Fois  (Valeur 1.0, x                  ) -> x
    | Fois  (x         , Valeur 1.0         ) -> x
    | Fois  (x         , Valeur 0.0         ) -> Valeur 0.0
    | Fois  (Valeur 0.0, x                  ) -> Valeur 0.0
    | Fois  (x         , Sur (Valeur 1.0, y)) -> Sur (x, y)
    | Sur   (Valeur 0.0, x                  ) -> Valeur 0.0
    | Sur   (x         , Valeur 1.0         ) -> x
    | x                                       -> x
  in
     match f with 
         Opp a             -> simple (Opp (simplifie a))
       | Plus (a,b)        -> simple (Plus (simplifie a, simplifie b))
       | Fois (a,b)        -> simple (Fois (simplifie a, simplifie b))
       | Moins (a,b)       -> simple (Moins(simplifie a, simplifie b))
       | Sur (a,b)         -> simple (Sur  (simplifie a, simplifie b))
       | Fonction (f,x)    -> Fonction (f,simplifie x)
       | DFonction (f,a,x) -> DFonction (f,a,simplifie x)
       | x              -> x;;
Il est souvent utile de remplacer une inconnue par une formule dans une formule
let f = Sur (Inconnue "x", Plus (Inconnue "x",Inconnue "y"));;
string_of_formule f;;
- : string = "(x) / ((x) + (y))"
let g = substitue f "x" (Fonction ("sin",Inconnue "y"));;
string_of_formule g;;
- : string = "(sin(y)) / ((sin(y)) + (y))"




let rec substitue = 
  function f    ->
  function x    ->
  function expr ->
    match f with 
      Inconnue i        when i=x -> expr
    | Opp (a)                    -> Opp   (substitue a x expr)
    | Plus (a,b)                 -> Plus  (substitue a x expr, substitue b x expr) 
    | Fois (a,b)                 -> Fois  (substitue a x expr, substitue b x expr)
    | Moins (a,b)                -> Moins (substitue a x expr, substitue b x expr)
    | Sur (a,b)                  -> Sur   (substitue a x expr, substitue b x expr)
    | Fonction (f,a)             -> Fonction (f,substitue a x expr)
    | DFonction (f,b,a)          -> DFonction (f,b,substitue a x expr)
    | a                          -> a;;
On peut commencer la dérivation:
let h = derive f "z";;
let hh = simplifie h;;

let g  = derive f "x";;
let gg = simplifie g;;

string_of_formule h;;
- : string = "(((0.) * ((x) + (y))) - ((x) * ((0.) + (0.)))) / (((x) + (y)) * ((x) + (y)))"
string_of_formule hh;;
- : string = "0."
string_of_formule g;;
- : string = "(((1.) * ((x) + (y))) - ((x) * ((1.) + (0.)))) / (((x) + (y)) * ((x) + (y)))"
string_of_formule gg;;
- : string = "(((x) + (y)) - (x)) / (((x) + (y)) * ((x) + (y)))"









let rec derive = 
  function f ->
  function x ->
    match f with 
      Valeur a            -> Valeur 0.0
    | Opp a               -> Opp (derive a x)
    | Inconnue a when a=x -> Valeur 1.0  
    | Inconnue a          -> Valeur 0.0  
    | Plus (a,b)          -> Plus (derive a x, derive b x)
    | Moins (a,b)         -> Moins (derive a x, derive b x)
    | Fois (a,b)          -> Plus (Fois (derive a x, b), Fois (a, derive b x))
    | Sur (a,b)           -> Sur (Moins (Fois (derive a x, b), 
                                         Fois (a, derive b x)),
                                  Fois (b,b))
    | Fonction (f,a)      -> Fois( DFonction (f,x,a) , derive a x )
    | a                   -> failwith ("Impossible de dériver "^(string_of_formule a)^" par rapport à "^x^".");;
Si l'on connaît la valeur formelle de certaines dérivées, on peut s'en servir pour remplacer les termes en DFonction. On peut stocker ces dérivées formelles dans une liste de paires, où au nom de la fonction est associé sa définition.
let derivees_usuelles = [
  ("log",Sur (Valeur 1.0,Inconnue "x"));
  ("exp",Fonction ("exp",Inconnue "x"));
  ("tan",Plus (Valeur 1.0, Fois (Fonction ("tan",Inconnue "x"), Fonction ("tan",Inconnue "x"))));
  ("sin",Fonction ("cos",Inconnue "x"));
  ("cos",Opp (Fonction ("sin",Inconnue "x")))
];;

string_of_formule (retrouve "tan" derivees_usuelles);;

let rec retrouve_derivee =
  function cle ->
  function
      []                                      -> Fonction (cle^"'",Inconnue "x")
    | (la_cle,la_valeur)::_ when la_cle = cle -> la_valeur
    | _::r                                    -> retrouve_derivee cle r;;

string_of_formule (retrouve_derivee "tan" derivees_usuelles);;
string_of_formule (retrouve_derivee "f" derivees_usuelles);;
On peut maintenant remplacer les DFonction par les valeurs contenues dans la liste
let f = Fonction ("log",Sur (Inconnue "y",Inconnue "x"));;
string_of_formule f;;
- : string = "log((y) / (x))"
let g = simplifie (derive f "x");;
string_of_formule g;;
- : string = "(dlog/dx((y) / (x))) * ((-(y)) / ((x) * (x)))"
let g = simplifie(remplace_dfonction derivees_usuelles g);;
string_of_formule g;;
- : string = "((1.) / ((y) / (x))) * ((-(y)) / ((x) * (x)))"




let rec remplace_dfonction =
  function l ->
  function 
      DFonction (f,x,exp) -> substitue (retrouve_derivee f l) x exp
    | Opp a               -> Opp (remplace_dfonction l a)
    | Plus  (a,b)         -> Plus  (remplace_dfonction l a, remplace_dfonction l b)
    | Moins (a,b)         -> Moins (remplace_dfonction l a, remplace_dfonction l b)
    | Fois  (a,b)         -> Fois  (remplace_dfonction l a, remplace_dfonction l b)
    | Sur   (a,b)         -> Sur   (remplace_dfonction l a, remplace_dfonction l b)
    | Fonction (f,x)      -> Fonction (f, remplace_dfonction l x)
    | x                   -> x;;