Récursivité mutuelle - Mutual recursion

En mathématiques et en informatique , la récursivité mutuelle est une forme de récursivité dans laquelle deux objets mathématiques ou informatiques, tels que des fonctions ou des types de données, sont définis l'un par rapport à l'autre. La récursivité mutuelle est très courante dans la programmation fonctionnelle et dans certains domaines problématiques, tels que les analyseurs de descente récursive , où les types de données sont naturellement mutuellement récursifs.

Exemples

Types de données

Informations complémentaires : type de données récursif

L'exemple de base le plus important d'un type de données pouvant être défini par récursivité mutuelle est un arbre , qui peut être défini mutuellement récursivement en termes de forêt (une liste d'arbres). Symboliquement: 

f: [t[1], ..., t[k]]
t: v f

Une forêt f consiste en une liste d'arbres, tandis qu'un arbre t consiste en une paire d'une valeur v et d'une forêt f (ses enfants). Cette définition est élégante et facile à travailler de manière abstraite (comme pour prouver des théorèmes sur les propriétés des arbres), car elle exprime un arbre en termes simples : une liste d'un type et une paire de deux types. De plus, il correspond à de nombreux algorithmes sur les arbres, qui consistent à faire une chose avec la valeur et une autre chose avec les enfants.

Cette définition mutuellement récursive peut être convertie en une définition récursive unique en insérant la définition d'une forêt : 

t: v [t[1], ..., t[k]]

Un arbre t se compose d'une paire d'une valeur v et d'une liste d'arbres (ses enfants). Cette définition est plus compacte, mais un peu plus désordonnée: un arbre se compose d'une paire d'un type et d'une liste d'un autre, qui nécessitent un démêlage pour prouver les résultats.

Dans Standard ML , les types de données tree et forest peuvent être mutuellement définis de manière récursive comme suit, permettant des arbres vides : 

datatype 'a tree = Empty | Node of 'a * 'a forest
and      'a forest = Nil | Cons of 'a tree * 'a forest

Fonctions informatiques

Tout comme les algorithmes sur les types de données récursifs peuvent naturellement être donnés par des fonctions récursives, les algorithmes sur des structures de données mutuellement récursives peuvent naturellement être donnés par des fonctions mutuellement récursives. Les exemples courants incluent les algorithmes sur les arbres et les analyseurs de descente récursive . Comme pour la récursivité directe, l' optimisation des appels de queue est nécessaire si la profondeur de récursivité est grande ou illimitée, comme l'utilisation de la récursivité mutuelle pour le multitâche. Notez que l'optimisation des appels de queue en général (lorsque la fonction appelée n'est pas la même que la fonction d'origine, comme dans les appels récursifs de queue) peut être plus difficile à mettre en œuvre que le cas particulier de l'optimisation d'appels récursifs de queue, et donc une implémentation efficace de la récursivité de queue mutuelle peut être absente des langages qui optimisent uniquement les appels récursifs de queue. Dans les langages tels que Pascal qui nécessitent une déclaration avant utilisation, les fonctions mutuellement récursives nécessitent une déclaration directe , car une référence directe ne peut pas être évitée lors de leur définition.

Comme pour les fonctions directement récursives, une fonction wrapper peut être utile, les fonctions mutuellement récursives étant définies comme des fonctions imbriquées dans sa portée si cela est pris en charge. Ceci est particulièrement utile pour partager l'état entre un ensemble de fonctions sans avoir à passer des paramètres entre elles.

Exemples de base

Un exemple type de récursivité mutuelle, certes artificielle, détermine si un nombre non négatif est pair ou impair en définissant deux fonctions distinctes qui s'appellent, en décrémentant de 1 à chaque fois. En C : 

bool is_even(unsigned int n) {
    if (n == 0)
        return true;
    else
        return is_odd(n - 1);
}

bool is_odd(unsigned int n) {
    if (n == 0)
        return false;
    else
        return is_even(n - 1);
}

Ces fonctions sont basées sur l'observation que la question est 4 pair ? est équivalent à est 3 impair ? , qui est à son tour équivalent à 2 pair ? , et ainsi de suite jusqu'à 0. Cet exemple est une récursivité mutuelle unique et pourrait facilement être remplacé par une itération. Dans cet exemple, les appels mutuellement récursifs sont des appels de queue et l'optimisation des appels de queue serait nécessaire pour s'exécuter dans un espace de pile constant. En C, cela prendrait O ( n ) espace de pile, à moins qu'il ne soit réécrit pour utiliser des sauts au lieu d'appels. Cela pourrait être réduit à une seule fonction récursive is_even. Dans ce cas, is_odd, qui pourrait être inline, appellerait is_even, mais is_evenne s'appellerait que lui-même.

Comme classe d'exemples plus générale, un algorithme sur un arbre peut être décomposé en son comportement sur une valeur et son comportement sur les enfants, et peut être divisé en deux fonctions mutuellement récursives, l'une spécifiant le comportement sur un arbre, appelant la forêt fonction pour la forêt d'enfants, et une spécifiant le comportement sur une forêt, appelant la fonction tree pour l'arbre dans la forêt. En Python : 

def f_tree(tree) -> None:
    f_value(tree.value)
    f_forest(tree.children)

def f_forest(forest) -> None:
    for tree in forest:
        f_tree(tree)

Dans ce cas, la fonction tree appelle la fonction forest par récursivité unique, mais la fonction forest appelle la fonction tree par récursivité multiple .

En utilisant le type de données Standard ML ci-dessus, la taille d'un arbre (nombre de nœuds) peut être calculée via les fonctions mutuellement récursives suivantes : 

fun size_tree Empty = 0
  | size_tree (Node (_, f)) = 1 + size_forest f
and size_forest Nil = 0
  | size_forest (Cons (t, f')) = size_tree t + size_forest f'

Un exemple plus détaillé dans Scheme, en comptant les feuilles d'un arbre : 

(define (count-leaves tree)
  (if (leaf? tree)
      1
      (count-leaves-in-forest (children tree))))

(define (count-leaves-in-forest forest)
  (if (null? forest)
      0
      (+ (count-leaves (car forest))
         (count-leaves-in-forest (cdr forest)))))

Ces exemples se réduisent facilement à une seule fonction récursive en insérant la fonction forest dans la fonction tree, ce qui est couramment fait dans la pratique : les fonctions directement récursives qui opèrent sur les arbres traitent séquentiellement la valeur du nœud et récursent sur les enfants au sein d'une fonction, plutôt que de les diviser en deux fonctions distinctes.

Exemples avancés

Un exemple plus compliqué est donné par les analyseurs de descente récursifs , qui peuvent être naturellement implémentés en ayant une fonction pour chaque règle de production d'une grammaire, qui se récurent alors mutuellement; ce sera en général une récursivité multiple, car les règles de production combinent généralement plusieurs parties. Cela peut également se faire sans récursivité mutuelle, par exemple en ayant toujours des fonctions séparées pour chaque règle de production, mais en les faisant appeler par une seule fonction de contrôleur, ou en mettant toute la grammaire dans une seule fonction.

La récursivité mutuelle peut également implémenter une machine à états finis , avec une fonction pour chaque état, et une récursivité unique dans un état changeant ; cela nécessite une optimisation des appels de queue si le nombre de changements d'état est important ou illimité. Cela peut être utilisé comme une forme simple de multitâche coopératif . Une approche similaire au multitâche consiste à utiliser à la place des coroutines qui s'appellent, où plutôt que de se terminer en appelant une autre routine, une coroutine cède à une autre mais ne se termine pas, puis reprend l'exécution lorsqu'elle est cédée. Cela permet aux coroutines individuelles de conserver leur état, sans qu'il soit nécessaire de les passer par des paramètres ou de les stocker dans des variables partagées.

Il existe également des algorithmes qui ont naturellement deux phases, tels que minimax (min et max), qui peuvent être implémentés en ayant chaque phase dans une fonction distincte avec récursivité mutuelle, bien qu'ils puissent également être combinés en une seule fonction avec récursivité directe.

Fonctions mathématiques

En mathématiques, les séquences Hofstadter Female et Male sont un exemple de paire de séquences entières définies de manière mutuellement récursive.

Les fractales peuvent être calculées (jusqu'à une résolution donnée) par des fonctions récursives. Cela peut parfois être fait plus élégamment via des fonctions mutuellement récursives ; la courbe de Sierpiński en est un bon exemple.

Prévalence

La récursivité mutuelle est très courante dans la programmation fonctionnelle et est souvent utilisée pour les programmes écrits en LISP , Scheme , ML et des langages de programmation similaires . Par exemple, Abelson et Sussman décrivent comment un évaluateur méta-circulaire peut être utilisé pour implémenter LISP avec un cycle eval-apply. Dans des langages tels que Prolog , la récursivité mutuelle est presque inévitable.

Certains styles de programmation découragent la récursivité mutuelle, affirmant qu'il peut être déroutant de distinguer les conditions qui renverront une réponse des conditions qui permettraient au code de s'exécuter indéfiniment sans produire de réponse. Peter Norvig souligne un modèle de conception qui décourage complètement l'utilisation, déclarant :

Si vous avez deux fonctions mutuellement récursives qui modifient toutes les deux l'état d'un objet, essayez de déplacer presque toutes les fonctionnalités dans une seule des fonctions. Sinon, vous finirez probablement par dupliquer le code.

Terminologie

La récursivité mutuelle est également connue sous le nom de récursivité indirecte , par opposition à la récursivité directe , où une seule fonction s'appelle directement. Il s'agit simplement d'une différence d'accentuation, et non d'une notion différente: la "récursion indirecte" met l'accent sur une fonction individuelle, tandis que la "récursion mutuelle" met l'accent sur l'ensemble des fonctions et ne distingue pas une fonction individuelle. Par exemple, si f s'appelle, c'est la récursivité directe. Si à la place f appelle g et alors g appelle f, qui à son tour appelle à nouveau g , du point de vue de f seul, f est indirectement récursif, tandis que du point de vue de g seul, g est indirectement récursif, tandis que du point de vue du point de vue des deux, f et g se reproduisent mutuellement. De même, un ensemble de trois fonctions ou plus qui s'appellent peut être appelé un ensemble de fonctions mutuellement récursives.

Conversion en récursivité directe

Mathématiquement, un ensemble de fonctions mutuellement récursives sont primitives récursives , ce qui peut être prouvé par récursivité du cours des valeurs , en construisant une fonction unique F qui répertorie les valeurs de la fonction récursive individuelle dans l'ordre : et en réécrivant la récursivité mutuelle en tant que récursivité primitive .

Toute récursivité mutuelle entre deux procédures peut être convertie en récursivité directe en insérant le code d'une procédure dans l'autre. S'il n'y a qu'un seul site où une procédure appelle l'autre, c'est simple, mais s'il y en a plusieurs, cela peut impliquer une duplication de code. En termes de pile d'appels, deux procédures mutuellement récursives produisent une pile ABABAB..., et l'incorporation de B dans A produit la récursivité directe (AB)(AB)(AB)...

Alternativement, n'importe quel nombre de procédures peut être fusionné en une seule procédure qui prend comme argument un enregistrement variant (ou type de données algébriques ) représentant la sélection d'une procédure et de ses arguments ; la procédure fusionnée se répartit ensuite sur son argument pour exécuter le code correspondant et utilise la récursivité directe pour appeler self le cas échéant. Cela peut être vu comme une application limitée de la défonctionnalisation . Cette traduction peut être utile lorsque l'une des procédures mutuellement récursives peut être appelée par du code extérieur, il n'y a donc aucun cas évident pour incorporer une procédure dans l'autre. Un tel code doit ensuite être modifié pour que les appels de procédure soient effectués en regroupant les arguments dans un enregistrement variant comme décrit ; alternativement, des procédures wrapper peuvent être utilisées pour cette tâche.

Voir également

Les références

Liens externes