Discussion :

[larchicha]

Bonsoir à toutes et à tous,

Je suis devant un bout de code en Ocaml et ayant vu récemment cette notion en cours, j'ai essayé de l'appliquer mais sans succès... j'aimerais donc, si vous le permettez, comprendre cette notion avec vous.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
let rec mrg l1 l2 = 
  match l1 with 
    |[] -> l2
    |h1::r1 -> begin
	  match l2 with
              |[] -> l1
	      |h2::r2 -> if h1 <= h2 then h1::(mrg r1 l2) else h2::(mrg l1 r2)
      end;;

Pourquoi cette fonction n'est donc pas récusive terminale ?
Le résultat n'est il pas en position terminale ?

Est-ce à cause de " h2::r2 -> ......" ? car on doit d'abord réaliser le test
"if h1 <= h2 " donc les 2 appels suivants sont mis en attente ?

J'suis perdu !
Merci d'avance pour le temps que vous m'accorderez.

[Cacophrene]

Bonsoir,

Quand une fonction est récursive terminale, le dernier appel récursif donne le résultat final. Dans le cas de la fonction merge ci-dessus, il faut remonter les appels récursifs pour effectuer les opérations de consing ( :: ) et construire la liste finale. Je t'invite à comparer ces deux fonctions très simples sur les listes OCaml :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
let rec length = function
  | [] -> 0
  | _ :: t -> 1 + length t

let length_rec_term  t=
  let rec loop count = function
    | [] -> count
    | _ :: t -> loop (count + 1) t
  in loop 0 t

Dans la première fonction, le calcul de length t est suivi par une addition (+ 1) et le cas de la liste vide correspond à une longueur nulle. Il faut donc bien remonter les appels récursifs pour calcul la somme finale. Dans la seconde fonction, qui est récursive terminale, il n'y a aucun calcul à effectuer après l'appel récursif de loop et le cas de la liste vide est le résultat attendu count. En effet, les appels récursifs emportent avec eux les résultats intermédiaires. Si tu remplaces l'addition par le consing, tu es à peu de choses près dans la même situation que merge.

Il faut faire attention à la notion de "calcul en position terminale". Quelquefois, on peut casser la récursivité terminale de façon assez subtile. C'est notamment le cas avec les structures de type try... with qui englobent les appels récursifs.

Cordialement,
Cacophrène

[larchicha]

T'es toujours aussi au taquet Cacophrene...

Quand tu parles de "remonter les appels récursifs"... tu veux dire rappeler un certain nombre de fois la fonction qu'on est entrain de définir, avant d'obtenir le résultat final ?

Sinon ,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
let length_rec_term  t=
  let rec loop count = function
    | [] -> count
    | _ :: t -> loop (count + 1) t
  in loop 0 t

La fonction auxiliaire "loop" prend 1 ou 2 arguments ? [ " loop (count + 1) t "]
ou il s'agit de la curryfication ? ( f x y = (f x) y ) ?

Merci.
PS : Tu gères la fougère...

[larchicha]

Je prends le cas de cette fonction :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 let rec aux x acc =
    if x <= 1
    then acc
    else aux (x - 1) (x + acc)
  in
    aux x 1;;

Le dernier appel récursif est situé après le "else" et ne nécessite aucun calcul ultérieur pour obtenir le résultat final... donc c'est une fonction récursive terminale ? (Je teste si j'ai compris le fond du fond de Planta... *sort*)

Merci.

[gasche]

Oui, la fonction écrite est bien tail-rec (d'ailleurs en remplaçant (x+acc) par (x*acc) tu obtiens une expression tailrec de la fonction factorielle). Le fait de passer plusieurs arguments à la fois est toujours considéré comme "une seule opération" (ce n'est pas tout à fait évident).

Je parle un peu plus de la récursion terminale dans un document publié sur un autre site, qui essaie en particulier de donner une explication intuitive de sa consommation mémoire réduite (pile d'appel).

[larchicha]

Je parle un peu plus de la récursion terminale dans ce document,[...]

Tu es l'auteur de ce document ? (à savoir bluestorm)

Edit : Vu la photo de profil, je suppose que oui...
Edit 2 : Sans lèche-botterie aucune, c'est un plaisir et un honneur de recevoir des explications de ta part... en "direct" du moins.

Edit 3 : Dans le cas où je veux rendre ma fonction "mrg" récursive terminale..

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
let mrg l1 l2 =
 let rec aux acc l1 l2 = 
      match l1 with
	|[] -> acc::l2
	|h1::r1 -> begin
	      match l2 with
		|[] -> acc::l1
		|h2::r2 -> if (h2 <= h1) then aux (h1::acc) r1 l2 
                     else aux (h2::acc) l1 r2
         end
in aux [] l1 l2 ;;
;;

C'est clairement faux mais voici ce qui se passe dans ma tête :
Je déclare une fonction auxiliaire qui prend 2 listes et un element "neutre" acc.
Je reprends le code de ma fonction non terminale et j'obtiens une erreur sur

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

h2::r2 -> if (h2 <= h1) then aux (h1::acc) r1 l2

de type

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

This expression has type 'a list but is here used with type 'a

.

La logique est sûrement fausse... mais j'ai essayé de faire en sorte que le dernier appel récursif amène au résultat final...

Merci d'avance.

[Cacophrene]

Bonjour,

Regarde cette fonction (attention code non testé) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
let merge l1 l2 =
  let rec loop acc l1 l2 =
    match l1, l2 with
    | [], [] -> acc
    | l1, [] -> List.rev_append acc l1
    | [], l2 -> List.rev_append acc l2
    | h1 :: t1, h2 :: t2 -> 
      let h, l1, l2 = if h1 <= h2 then h1, t1, l2 else h2, l1, t2 in
      loop (h :: acc) l1 l2
  in loop [] l1 l2

Principe : on fait des appels récursifs pour créer le prefixe acc en triant les éléments, et ceux-ci sont ajoutés par consing, de sorte que acc contient les éléments en ordre inversé. Ensuite, on utilise List.rev_append pour la dernière concaténation, à la place de l'opérateur @, ce qui nous permet de rétablir l'ordre des éléments.

Remarque : sur le plan de la complexité de cette fonction, il y a un surcoût lié à List.rev_append.

Cordialement,
Cacophrène