Récursivité structurelle
Un article de Mangue.org, l'encyclopéde libre.
La récursivité est indispensable à la résolution de problèmes complexes en programmation fonctionnelle. Nous allons la présenter progressivement...
| Sommaire |
La récursivité dans les mathématiques
Les mathématiques sont pleines de fonctions récursives. Vous connaissez certainement déjà la fonction factorielle notée n! et qu'on lit "factorielle de n". Comme la plus part des fonctions récursives en mathématiques celle-ci admet un cas simple, 0! = 1, et un cas général, n! = n * (n-1)!
Les fonctions récursives en Caml présentent plusieurs cas. Pour la fonction factorielle vous connaissez maintenant le cas simple et le cas général. Nous définirons cette fonction par filtrage afin d'en faciliter la lisibilité (on pourrait introduire une condition dans l'expression fonctionnelle). Pour définir une fonction récursive en Caml il faut faire précéder son nom par le mot clé rec comme dans l'exemple suivant :
# let rec factorielle = fun
| 0 -> 1
| n -> if (n<0) then
invalid_arg "factorielle: cette fonction n'est définie que pour les entiers positifs"
else
n * factorielle (n-1) ;;
factorielle : int -> int = <fun>
# factorielle (-1) ;;
Uncaught exception: Invalid_argument
"factorielle: cette fonction n'est définie que pour les entiers positifs"
# factorielle (11) ;;
- : int = 39916800
| Astuce |
Si nous avions omis le mot clé rec le compilateur nous indiquerait que l'identificateur factorielle est inconnu ; à juste titre puisque nous tenterions d'utiliser une fonction pas encore définie.
|
Le stockage en mémoire des fonctions récursives est un peu différent de la mémorisation des fonctions les plus simples. Pour plus de détails lisez l'annexe correspondante.
Optimisation en Caml
Nous allons prendre l'exemple d'une autre fonction mathématique, cnp, soit le nombre de combinaisons de p objets parmis n.
Rappel mathématique : cnp n'est définie que pour des entiers positifs cnp (n,0) = 1 Si p > n Alors cnp (n,p) = 0 cnp (n,p) = cnp (n-1,p) + cnp (n-1,p-1)
Voilà même si vous n'entendez pas vraiment l'utilité d'une telle fonction (pour être honnète je n'en ai qu'un vague souvenir moi même), vous avez tous les éléments nécessaires pour la coder en Caml.
# let rec cnp = fun
| (n,0) ->
if ( n >= 0)
then 1 (* cas simple *)
else invalid_arg "cnp: argument négatif"
| (n,p) ->
if ( ( n < p) && ( n > 0))
then 0 (* cas simple *)
else if ( ( p > 0) && ( n > 0))
then cnp (n-1,p) + cnp (n-1,p-1) (* cas général *)
else invalid_arg "cnp: argument négatif" ;;
cnp : int * int -> int = <fun>
# cnp (7,6) ;;
- : int = 7
# cnp (4,6) ;;
- : int = 0
# cnp (4,2) ;;
- : int = 6
# cnp (-1,0) ;;
Uncaught exception: Invalid_argument "cnp: argument négatif"
Observez bien le corps de cette fonction. Dans son cas général celle-ci s'appelle deux fois. Celà implique que plus le nombre d'appels récursifs de la fonction est important plus son exécution occupera d'espace mémoire. La plus part des fonctions peuvent être modifiées de façon à éviter dette "gourmandise" qui se traduit aussi par un retard d'exécution, mais ce n'est pas l'objet de ce cours puisque ça fait souvent appel à des notions avancées en mathématiques.
Application aux types de données
Nous verrons dans un prochain cours comment implémenter des types de données récursifs. Pour le moment nous allons nous concentrer sur quelques exemples de fonctions récursives opérant sur les entiers ou les chaînes de caractères.
Tous les nombres entiers s'écrivent en juxtaposant des chiffres. On se propose d'écrire une fonction prenant en argument un nombre entier et renvoyant en résultat son chiffre de poids fort (c'est à dire le plus à gauche). Voici une solution possible :
# let rec poids_fort = fun n -> if (n < 10) (* alors c'est un chiffre *) then n else poids_fort (n / 10) ;; poids_fort : int -> int = <fun> # poids_fort (5) ;; - : int = 5 # poids_fort (1563) ;; - : int = 1
Essayez d'écrire sur le même principe la fonction plus_grand renvoyant le plus grand chiffre du nombre passé en argument.
Ecrivez aussi la fonction plus_grand pour une chaîne de caractère, elle renverra le caractère dont le code ASCII es le plus élevé dans la chaîne.
Si vous avez des problèmes, posez vos questions sur le forum comme toujours.
De même une chaîne de caractères est une suite de caractères. Nous avons vu dans le deuxième cours comment indexer les carctères d'une chaîne. Nous allons écrire ensemble la focntion mid isolant une partie de la chaîne de caractère passée en arguement.
Les trois arguments de cette chaîne seront dans l'ordre, le rang du premier caractère, le rang du dernier caractère et enfin la chaîne de caractère elle même. Voici une correction possible :
# let rec mid = fun
| _ _ "" -> "" (* cas simple *)
| inf sup chaine ->
if ( inf > sup)
then failwith "mid: mauvais ordre des bornes"
else if ( ( inf < 0) || ( sup <= 0))
then invalid_arg "mid: bornes incorrectes"
else if ( sup > string_length ( chaine))
then failwith "mid: chaine trop courte"
else if (inf = sup)
then "" (* cas simple *)
else (* cas général *)
( string_of_char( chaine.[inf])) ^ ( mid (inf+1) sup chaine) ;;
mid : int -> int -> string -> string = <fun>
# mid 5 11 "CAML est un langage fonctionnel" ;;
- : string = "est un"
# mid 4 3 "encore un essai" ;;
Uncaught exception: Failure "mid: mauvais ordre des bornes"
Je suis entièrement d'accord avec vous lorsque vous pensez que c'est une fonction complexe. C'est vrai, mais gardez la quand même sur un bout de papier vous en aurez peut-être besoin pour la suite. En vous y penchant un peu vous devriez pouvoir comprendre sans trop de problèmes ; si des doutes persistes vous savez où poser votre question.
Nous souhaitons maintenant définir les fonctions début et fin pour une chaîne de caractère. La première renverra une chaîne composée uniquement du premier caractère de son argument alors que la seconde renverra tous les caractères de cette chaîne à l'exception du premier.
# let début = mid 0 1 and fin (chaine) = mid 1 (string_length (chaine) - 1) chaine ;; début : string -> string = <fun> fin : string -> string = <fun> # début "Voici une fonction définie à partie de mid" ;; - : string = "V" # fin "En voici une autre ;)" ;; - : string = "n voici une autre ;)"
Cas des focntiosn récursives à plusieurs arguments
Examinez la fonction long_base qui suit. Celle-ci est chargée de déterminée combien de chiffres composeront le nombre si on l'écrit en base b :
# let rec long_base = fun | b 0 -> 0 | b n -> 1 + long_base b (n/b) ;; long_base : int -> int -> int = <fun> # long_base 16 256 ;; - : int = 3 # long_base 2 35 ;; - : int = 6 # trace "long_base" ;; The function long_base is now traced. - : unit = () # long_base 8 127 ;; long_base <-- 8 long_base --> <fun> long_base* <-- 127 long_base <-- 8 long_base --> <fun> long_base* <-- 15 long_base <-- 8 long_base --> <fun> long_base* <-- 1 long_base <-- 8 long_base --> <fun> long_base* <-- 0 long_base* --> 0 long_base* --> 1 long_base* --> 2 long_base* --> 3 - : int = 3 # untrace "long_base" ;; The function long_base is no longer traced. - : unit = ()
| Astuce |
La fonction trace permet de suivre ce qu'il se passe à chaque appel récursif de la fonction. Vous pouvez l'invoquer pour n'importe quelle fonction récursive, mais pensez à désactivé le suivi de la fonction avec untrace ;)
|
Vous voyez très bien que la fonction long_base est appellée plusieurs fois avec le même argument b. En effet celui-ci apparaît dans chacun des filtres de la fonction mais n'intervient pas dans la sélection des cas. Concrètement il convient de définir localement une fonction afin qu'il n'y ait pas d'appels inutiles.
Je le répète plus une fonction est appellée récursivement et plus elle utilise de ressources systèmes pour l'exécution (temps) et pour le stockage en mémoire.
Voici une version améliorée de la fonction long_base, nous définissons localement une fonction récursive chargée d'effectuer les calculs nécessaires.
# let long_base b =
let rec aux = fun
| 0 -> 0
| n -> 1 + aux (n/b)
in
aux ;;
long_base : int -> int -> int = <fun>
# trace "long_base" ;;
The function long_base is now traced.
- : unit = ()
# long_base 8 127 ;;
long_base <-- 8
long_base --> <fun>
long_base* <-- 127
long_base* --> 3
- : int = 3
# untrace "long_base" ;;
The function long_base is no longer traced.
- : unit = ()
Vous voyez par vous même que le nombre d'appels récursifs à considérablement été réduit. Pensez-y ! Dès qu'une de vos fonctions récursives est appellée avec un paramètre qui ne varie jamais d'un appel à l'autre c'est que vous avez certianement une meilleure façon d'écrire la même fonction. Non seulement elle est plus lisible mais en plus elle est bien plus optimisée pour le processeur :)
