Qu'est-ce que ce genre de « récursion » mutuelle appelé?

Question

Mon problème est avec un certain style de code qui ressemble beaucoup à récursivité, mais pas tout à fait qui. La récursivité est, pour ne citer Wikipedia « , un procédé de définition des fonctions dans lesquelles la fonction étant définie est appliquée dans sa propre définition ». De même récursion mutuelle applique une autre fonction qui, directement ou indirectement, applique la fonction que nous définissons.

Le problème est que le code que je pense, et de traiter, ne pas utiliser la même fonction! Il utilise le même code dans une autre fonction (comme une méthode ou fermeture).

Le problème ici est que si mon code est le même, les fonctions ne sont pas. Jetez un oeil un exemple de récursion mutuelle de base suivante:

def is_even(x):
    if x == 0:
        return True
    else:
        return is_odd(x - 1)

def is_odd(x):
    if x == 0:
        return False
    else:
        return is_even(x - 1)

Ceci est quelque peu intuitive, et très clairement mutuellement récursive. Cependant, si j'Envelopper chaque fonction comme une fonction intérieure qui est créé une fois que chaque appel, il devient moins clair:

def make_is_even(): 
    def is_even(x):
        if x == 0:
            return True
        else:
           return make_is_odd()(x - 1)
    return is_even

def make_is_odd(): 
    def is_odd(x):
        if x == 0:
            return False
        else:
            return make_is_even()(x - 1)
    return is_odd

def is_even2(x):
    return make_is_even()(x)

def is_odd2(x):
    return make_is_odd()(x)

optimisations comme Omettre memoization implicites, etc., cela produit une chaîne d'appels de fonctions qui ne sont pas strictement récursif, la création et appelant diverses nouvelles fonctions sans jamais appeler le même deux fois. Néanmoins toutes ces fonctions suivent un modèle commun, et ne sont que la même fonction créé maintes et maintes fois (peut-être avec différentes variables libres.

Et encore une fois, nous pouvons venir directement avec un équivalent (après tout, les classes sont vraiment seulement des fermetures, à droite;) la mise en œuvre en utilisant des classes. Cela est particulièrement important, étant donné que ce style de [insérer le nom ici] est utilisé, par exemple, le Motif composite. La différence est que le modèle de conception composite, et la plupart des utilisations (même des fermetures), les instances ne sont généralement pas créés à la volée. Il est encore essentiellement le même.

class EvenChecker(object):
    def check(self, x):
        if x == 0:
            return True
        else:
            return OddChecker().check(x - 1)

class OddChecker(object):
    def check(self, x):
        if x == 0:
            return False
        else:
            return EvenChecker().check(x - 1)

def is_even3(x):
    return EvenChecker().check(x)

def is_odd3(x):
    return OddChecker().check(x)

Cette fois, la chaîne est de la création d'objets et appels de méthode, mais le principe est le même. (Je note en fait que c'est un peu différent, en ce sens Python définit une simple enveloppe sur une base par objet lui-même appelle la même fonction à chaque time-- mais ce n'est pas nécessairement quelque chose que nous devons savoir, et n'a pas besoin d'être vrai pour d'autres implémentations des classes et des objets. Mais oui, à proprement parler, il est mutuellement récursive, ainsi que ... quelque chose de plus, et il est cette autre chose que je veux savoir.)

Answer 1

Comme vous le soulignez, cela est encore récursion mutuelle. Je ne pense pas que « quelque chose de plus » vous demandez a environ un nom; si elle ne je ne l'ai jamais entendu.

Answer 2

récursion mutuelle est un cas particulier de récursion indirecte .

Answer 3

Apparemment, il est appelé mutuelle Recursion :)

L'article donne même le même exemple que vous, avec des fonctions de odd? et even?.