Récursivité terminale en Caml, F#, Prolog...
Date de publication : à venir...
Par
Pierre Caboche (autres articles)
La récursivité terminale est une forme particulière de récursivité qui peut être
transformée en fonction impérative, plus rapide et consommant moins de mémoire.
C'est donc une notion très importante, notamment en programmation fonctionnelle.
Le but de cet article est de vous présenter la récursivité terminale afin d'en
comprendre le principe, l'intérêt et la mise en œuvre.
Introduction
Définition
Optimisation
Écrire une fonction récursive terminale
Application
En Caml
En Prolog
Résumé
Remerciements
Introduction
Récursivité
La récursivité, c'est le fait qu'une fonction s'appelle elle-même. En effet,
certains algorithmes sont plus faciles à exprimer de manière récursive.
Exemple: l'algorithme Quick sort (
code source extrait de wikipedia)
let rec quicksort = function
[] -> []
| pivot :: rest ->
let is_less x = x < pivot in
let left, right = List.partition is_less rest in
quicksort left @ [pivot] @ quicksort right
;;
|
À chaque appel d'une fonction, de la mémoire est allouée dans la pile ce qui,
en définitive, peut conduire à un dépassement de la capacité de la pile,
provoquant une erreur.
Récursivité terminale
La récursivité terminale est une forme particulière de récursivité pouvant être
optimisée afin de ne pas consommer de mémoire dans la pile.
Programmation fonctionnelle
Certains langages utilisent la récursivité de manière intensive. C'est notamment
le cas des langages fonctionnels (Lisp, Haskell, Caml, F#...) mais aussi des
langages de programmation logique (Prolog).
L'utilisation de la récursivité terminale permet donc d'améliorer la qualité des
programmes écrits dans les langages fonctionnels, des langages aux propriétés
étonnantes (j'espère pouvoir revenir sur ces capacités dans un prochain article).
C'est pourquoi il est important en programmation fonctionnelle de maîtriser la
récursivité terminale.
Des styles de programmation qui s'opposent...
Dans le monde des langages fonctionnels, tout compilateur digne de ce nom se
doit d'optimiser les fonctions récursives terminales. Dans le monde impératif,
c'est beaucoup moins le cas. À vrai dire, avec les langages impératifs on
utilise beaucoup moins la récursivité car on dispose des boucles (for, while, etc.).
En revanche, la programmation impérative est source d'un certain nombre de bugs
potentiels (variables non initialisées, effets de bord...) qui sont tout
simplement inexistants en programmation fonctionnelle.
La question de la récursivité terminale va donc bien au-delà de simples
questions d'optimisations : elle oppose deux styles de programmation, deux
catégories de langages diamétralement opposés.
D'un côté, la programmation impérative est la plus répandue, facile à comprendre
(il s'agit de définir des suites d'instructions à exécuter), performante (car
très proche des instructions exécutées par le processeur) mais apporte son
lot de bugs (NullPointer & Co...). D'un autre côté, la programmation fonctionnelle
est moins facilement accessible (il faut maîtriser des concepts tels que la
récursivité terminale, le pattern-matching...), très stricte
(langage très fortement typé) mais en contrepartie beaucoup plus sûre (limite
le risque d'erreurs à la compilation).
La programmation fonctionnelle demande une certaine rigueur mais apporte un
enseignement qui se révèle très bénéfique, y compris en programmation impérative.
L'apprentissage de la programmation fonctionnelle est donc très important
(même pour le programmeur impératif) mais pour bien connaître la programmation
fonctionnelle, il est indispensable de maîtriser la récursivité terminale.
C'est ce dont nous allons vous parler dans cet article.
Définition
 |
Une fonction f est dite "récursive terminale" si dans tous les cas, elle retourne :
|
- soit une valeur fixe
- soit le résultat d'un appel récursif à la fonction f
Exemples
Les fonctions suivantes ne sont pas récursives terminales :
let rec longueur = function
[] -> 0
| t :: q -> 1 + longueur q
;;
|
Cette fonction n'est pas récursive terminale car la valeur de retour
(1 + longueur q) ne respecte pas la définition.
let rec quicksort = function
[] -> []
| pivot :: rest ->
let is_less x = x < pivot in
let left, right = List.partition is_less rest in
quicksort left @ [pivot] @ quicksort right
;;
|
Les fonctions suivantes sont récursives terminales :
let factorielle n =
let rec auxiliaire resultat = function
0 -> resultat
| n -> auxiliaire (n * resultat) (n - 1)
in auxiliaire 1 n
;;
|
Optimisation
Pour le compilateur, il est possible de transformer les fonctions récursives
terminales en itérations, plus rapides et moins consommatrices de mémoire.
S'il n'y a pas récursivité terminale, à chaque appel récursif de la fonction,
le programme allouera un nouvel environnement d'exécution dans la pile, avec un
risque de dépassement de la capacité de la pile :
Fonction récursive non terminale
S'il y a récursivité terminale, le compilateur peut optimiser l'exécution :
Fonction récursive terminale
Lorsqu'il y a récursivité terminale, le compilateur fait en sorte que le
programme réutilise le même environnement d'exécution (seules les valeurs des
variables changent). Ainsi la fonction se comporte comme si elle avait été
écrite de manière itérative.
Écrire une fonction récursive terminale
Accumulateurs et variables auxiliaires
La plupart du temps (mais pas toujours !) pour transformer une fonction
récursive en fonction récursive terminale, on a besoin d'introduire de
nouvelles variables qu'on appelle, selon le cas, accumulateurs ou
variables auxiliaires. On les appelle ainsi car c'est grâce à elles que
l'on construit petit à petit le résultat. Lorsque la condition d'arrêt est
atteinte, ce sont généralement ces variables qui sont retournées comme
résultat de la fonction.
-
On parle d'accumulateur lorsqu'il s'agit d'une liste qui est
construite au fur et à mesure du déroulement de la fonction
-
On parle de variable auxiliaire lorsqu'il s'agit d'un paramètre dont
on modifie la valeur à chaque appel récursif de la fonction
Fonctions auxiliaires
Transformer une fonction récursive en fonction récursive terminale implique
donc généralement l'introduction de fonctions auxiliaires.
Une fonction auxiliaire est une fonction qui a en paramètres des accumulateurs
et/ou des variables auxiliaires. Le seul but d'une fonction auxiliaire est de
rendre récursive terminale la fonction appelante. La fonction auxiliaire n'a
donc pas besoin d'être accessible à l'utilisateur.
En Caml, il est possible de déclarer une fonction à l'intérieur d'une autre
fonction, de manière à limiter de la portée de la fonction interne (celle-ci ne
sera accessible qu'à l'intérieur de la fonction dans laquelle elle est déclarée).
Exemple avec la fonction factorielle :
| Fonction factorielle |
let factorielle n =
let rec auxiliaire resultat = function
0 -> resultat
| n -> auxiliaire (n * resultat) (n - 1)
in auxiliaire 1 n
;;
|
Ici, la fonction récursive terminale se présente ainsi :
-
le prototype de la fonction récursive terminale, telle qu'elle doit apparaître
à l'utilisateur
-
à l'intérieur de la fonction, déclaration de la fonction auxiliaire (avec
ses accumulateurs et/ou variables auxiliaires), inaccessible à l'utilisateur
- appel de la fonction auxiliaire
Ceci est un exemple classique de mise sous forme récursive terminale. Cependant
il n'est pas toujours facile de transformer une fonction récursive en fonction
récursive terminale... et d'ailleurs ce n'est pas toujours justifié.
En théorie, toute fonction récursive peut se mettre sous forme récursive
terminale (et donc sous forme itérative) en ajoutant des piles, mais dans ce
cas on déplace le problème : au lieu d'avoir des piles d'exécution on a des
piles de données et le programme est beaucoup moins lisible. Pour de telles
fonctions, la transformation en fonction récursive terminale ne se justifie pas.
Application
En Caml
En Caml, pour qu'une fonction soit récursive terminale, il faut qu'elle respecte
la définition décrite précédemment.
En d'autres termes, il faut que, quel que soit le résultat d'exécution de la
fonction, celui-ci représente
- soit une valeur fixe (qui peut être une valeur passée en paramètre)
- soit le résultat d'un appel récursif à la fonction
Exemple :
| Fonction factorielle |
let factorielle n =
let rec auxiliaire resultat = function
0 -> resultat
| n -> auxiliaire (n * resultat) (n - 1)
in auxiliaire 1 n
;;
|
En Prolog
En Prolog, on utilise des prédicats et non des fonctions. On ne peut donc pas
appliquer stricto sensu la définition de la récursivité terminale telle que
présentée précédemment.
L'exécution d'un programme Prolog est très différente des autres langages
(fonctionnels ou impératifs). Le déroulement d'un programme Prolog est décrit
dans
cet article,
mais nous allons en faire un résumé.
L'exécution d'un programme Prolog prend la forme d'un arbre, qu'on appelle
"arbre décisionnel". Chaque branche de l'arbre constitue ce que l'on appelle un
"point de choix". Lorsqu'une branche de l'arbre a été explorée (soit en retournant
une solution, soit en échouant), Prolog effectue un "retour arrière"
(=backtracking) afin de revenir au point de choix précédent en vue de trouver
de nouvelles solutions.
Chaque point de choix nécessite que soit sauvegardé l'état de l'exécution du
programme, ce qui consomme de la mémoire. Il est cependant possible de supprimer
des points de choix grâce à l'instruction "cut" ("!"), ou
"coupe-choix", ce qui aura pour effet de couper les branches précédent le point
de choix. N'ayant plus besoin de ces différents points de choix, Prolog peut
alors libérer de la mémoire dans la pile d'exécution.
Pour économiser de la mémoire, on a recours au "cut" ("!") et donc le prédicat
retournera au maximum une solution.
En Prolog, on a donc récursivité terminale si chaque clause d'un prédicat présente la structure suivante :
- condition logique (ensemble d'instructions n'introduisant pas de point de choix)
- "cut" ( ! )
- puis :
- soit unification des variables avec la solution
- soit appel récursif au prédicat
Cette structure correspond au
pattern de programmation décrit ici,
avec comme condition supplémentaire que les clauses se terminent soit par
l'unification des variables avec la solution, soit par un appel récursif au prédicat.
Exemple :
 |
TODO: mettre un exemple
|
On peut remarquer une différence notable entre l'implémentation Prolog et
l'implémentation fonctionnelle. Avec les langages fonctionnels, on implémente
les fonctions de manière qu'elles soient récursives terminale et c'est le
compilateur qui est chargé de supprimer la récursivité. En Prolog, le programmeur
insère des coupe-choix (!) afin de signaler au compilateur qu'il est possible de
libérer de la mémoire et qu'on ne fera pas de retour sur trace.
La deuxième approche (les coupe-choix en Prolog) est plus simple pour le
compilateur car le programmeur spécifie explicitement quand il est possible de
libérer de la mémoire (la libération effective de la mémoire peut éventuellement
être différée, comme c'est le cas dans les machines virtuelles, dans un but
d'optimisation). Avec les langages fonctionnels, c'est le compilateur qui doit
effectuer tout le travail pour éliminer la récursivité.
Bien que différentes, ces deux approches tendent vers le même but : supprimer
la récursivité, économiser de la mémoire et éviter les dépassements de capacité
de la pile.
Il est également à noter que, pour les puristes, le coupe-choix du Prolog est
considéré comme le 'goto' de la programmation logique : introduit pour des
raisons de performance, il nous éloigne de l'esprit originel de Prolog dans
lequel on décrit des solutions et non la manière dont le programme doit
s'exécuter. Dans ce cas il faut que le compilateur soit capable d'optimiser
le programme.
Résumé
Il est important de savoir reconnaître une fonction récursive, donc de se
souvenir de la définition :
|
Une fonction f est dite "récursive terminale" si dans tous les cas, elle retourne :
|
- soit une valeur fixe
- soit le résultat d'un appel récursif à la fonction f
Une fonction récursive terminale peut être transformée par le compilateur
en fonction itérative, plus performante.
Remerciements
Copyright © 2008 pcaboche.
Aucune reproduction, même partielle, ne peut être faite
de ce site ni de l'ensemble de son contenu : textes, documents, images, etc.
sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à
trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.
