Developpez.com

Une très vaste base de connaissances en informatique avec
plus de 100 FAQ et 10 000 réponses à vos questions

Developpez.com - Autres
X

Choisissez d'abord la catégorieensuite la rubrique :


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

info Une fonction f est dite "récursive terminale" si dans tous les cas, elle retourne :



Exemples

Les fonctions suivantes ne sont pas récursives terminales :

Source : wikipedia.
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 :

Source : wikipedia.
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
Fonction récursive non terminale



S'il y a récursivité terminale, le compilateur peut optimiser l'exécution :

Fonction récursive terminale
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.




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
;;
Source : wikipedia.




Ici, la fonction récursive terminale se présente ainsi :

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

Exemple :
Fonction factorielle
let factorielle n =
    let rec auxiliaire resultat = function
         0 -> resultat
       | n -> auxiliaire (n * resultat) (n - 1)
     in auxiliaire 1 n
;;
Source : wikipedia.


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 :

  1. condition logique (ensemble d'instructions n'introduisant pas de point de choix)
  2. "cut" ( ! )
  3. puis :
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 :

warning 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 :

info Une fonction f est dite "récursive terminale" si dans tous les cas, elle retourne :



Une fonction récursive terminale peut être transformée par le compilateur en fonction itérative, plus performante.


Remerciements






Valid XHTML 1.1!Valid CSS!

Copyright © 2008 pcaboche. Aucune reproduction, même partielle, ne peut être faite de ce site et 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.

Contacter le responsable de la rubrique Autres