Bonjour,
je ne comprends pas le principe de la récursivité terminale. Un exemple pour la fonction factorielle que j'ai trouvé:
# let factorielle n =
let rec auxiliaire resultat = function
0 -> resultat
| n -> auxiliaire (n * resultat) (n - 1)
in auxiliaire 1 n ;;
Pourriez-vous m'expliquer cette fonction en détail pour comprendre le principe de la récursivité terminale?
Merci beaucoup!

let factorielle n =
    let rec auxiliaire resultat = function
        0 -> resultat
      | n -> auxiliaire (n * resultat) (n - 1)
in auxiliaire 1 n

Cette fonction ('auxiliaire') est récursive terminale car elle termine par s'appeler. Elle n'a plus rien à faire après avoir s'être appelé elle-même.

let rec factorielle n = match n with
      0 -> 1
    | _ -> n * factorielle (n-1)

Dans ce cas là la fonction n'est pas récursive terminale car elle doit après avoir récupéré le résultat de 'factorielle (n-1)', elle doit le multiplier par n.

ok pour la déf de récursivité terminale. Maintenant j'aimerais comprendre la partie:
| n -> auxiliaire (n * resultat) (n - 1)
Je vois pas trop

(peut-être qu'avec un ex je comprendrais mieux??)
Merci!

Est-ce que tu connais le pattern matching ?
Bah cette ligne, ça fait partie de ça.

| n pour tester le 2ème paramètre de la fonction auxiliaire
-> auxiliaire (n * resultat) (n - 1) pour appeler récursivement la fonction auxiliaire avec 2 paramètres : le résultat et la 'valeur en cours'.

Grossomodo, tu calcules ta factorielle comme ça (pour 9!) : 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

La récursivité terminale est une "astuce" pour rendre certains codes plus efficaces : Lorsqu'on appelle une fonction, en temps normal, on doit se souvenir de l'endroit où on était pour pouvoir y retourner lorsque la fonction retourne un résultat.

Ainsi, dans la définition naïve de la factorielle, le calcul " n * fact (n - 1) " doit d'abord calculer l'appel récursif puis la multiplication.

fact 3
===  3 * fact 2
===  3 * (2 * fact 1)
===  3 * (2 * (1 * fact 0))
===  3 * (2 * (1 * 1))
===  (* Les multiplications peuvent maintenant s'effectuer *)
===  3 * (2 * 1)
===  3 * 2
===  6

Le problème, c'est qu'on doit conserver les valeurs des différents n en attente du calcul de la multiplication : cela consomme beaucoup trop de mémoire pour ce problème.

Une des astuces pour mettre en place la récursivité terminale, c'est de stocker le résultat du calcul comme un paramètre (ici "resultat") de la fonction. Lorsqu'on arrive à un cas terminal (non récursif), il suffit de retourner "resultat".

auxiliaire 1 3
===  auxiliaire (1 * 3) 2
===  auxiliaire (3 * 2) 1
===  auxiliaire (6 * 1) 0
===  6

Comme la multiplication peut s'effectuer tout de suite, il n'y a pas de perte de mémoire et le programme termine plus vite.

Citation : lastsseldon

Comme la multiplication peut s'effectuer tout de suite, il n'y a pas de perte de mémoire et le programme termine plus vite.

Le reste est très bien expliqué mais ceci me semble faux : la complexité temporelle est exactement la même. Le programme ne termine donc pas plus vite.
En revanche, on a aucun risque de faire exploser la mémoire.

Un autre avantage de la récursivité terminale est le principe de 'dérécursivation'. Pour une raison lambda, on peut avoir besoin de transformer une fonction récursive en fonction impérative. Produire une fonction équivalente n'est pas toujours aussi aisée que dans les exercices (ici, la fonction impérative est immédiate) et la récursivité terminale offre un confort dans ces cas-là.

La complexité temporelle a beau être la même, la version non tailrec doit néanmoins "revenir sur ses pas" (lorsque l'appel retourne un résultat -- s'il y a N appels, il y aura N retours.) Dans le cas d'un tailcall, on ne paye que l'appel de la fonction : elle n'a pas besoin de revenir. C'est minime, mais c'est une différence importante.

ok j'ai compris! Par-contre je trouve que la fct fact en récursive terminale est loin d'être évidente à trouver.
J'avais un autre problème ( ):
let rec objet l e = match l with
|[]->false
|t::q->e=t or objet q e;;
qui teste si un objet e est dans une liste l.
Cette fonction est récursive...terminale!
Pourtant elle ne termine pas par s' apeller si ??

(Essaie d'utiliser les balises <code type="ocaml"> ... </code> )
Si.
En fait, cela vient du || , qui est paresseux.
C'est-à-dire que, dans e = t || objet q e , le compilateur va d'abord évaluer la partie e = t , puis distingue deux cas :

• Soit il trouve "vrai", donc puisque la suite est un "OU", il n'y a pas besoin de tester le reste, et il retourne directement vrai
• Soit il trouve "faux", donc puisque la suite est un "OU", il ne reste plus qu'à retourner le résultat de objet q e , sans avoir besoin de conserver quoi que ce soit en mémoire ici, d'où récursivité terminale.

En fait, la fonction pourrait être réécrite (et la récursivité terminale est peut-être alors plus évidente ?) ainsi :

let rec objet l e = match l with
  | [] -> false
  | t::q when t = e -> true
  | t::q -> objet q e
;;

ok pigé!
Merci à tous!

11 ans plus tard 

@MAMADOUSALIOUDIALLO3 Bonjour, merci de ne pas déterrer d'ancien sujet résolu.

Déterrage

Citation des règles générales du forum :

Avant de poster un message, vérifiez la date du sujet dans lequel vous comptiez intervenir.

Si le dernier message sur le sujet date de plus de deux mois, mieux vaut ne pas répondre.
En effet, le déterrage d'un sujet nuit au bon fonctionnement du forum, et l'informatique pouvant grandement changer en quelques mois il n'est donc que rarement pertinent de déterrer un vieux sujet.

Au lieu de déterrer un sujet il est préférable :

• soit de contacter directement le membre voulu par messagerie privée en cliquant sur son pseudonyme pour accéder à sa page profil, puis sur le lien "Ecrire un message"
• soit de créer un nouveau sujet décrivant votre propre contexte
• ne pas répondre à un déterrage et le signaler à la modération

Je ferme ce sujet. En cas de désaccord, me contacter par MP.