Was ist diese Art der gegenseitigen „Rekursion“ genannt?

Question

ist mein Problem mit einem bestimmten Stil von Code, dass es sehr viel Rekursion ähnelt, ist aber nicht ganz das. Rekursion ist, zu zitieren Wikipedia „, ein Verfahren zur Definition Funktionen, in denen die Funktion angewendet wird, definiert, innerhalb ihrer eigenen Definition“. Ähnlich gegenseitige Rekursion gilt eine andere Funktion, die direkt oder indirekt die Funktion gilt wir definieren.

Das Problem ist, dass der Code die ich denke, und der Umgang mit, nicht die gleiche Funktion nutzen! Es verwendet die gleiche Code in einer anderen Funktion (als Methode oder Schließung).

Das Problem hier ist, dass, während mein Code gleich ist, sind die Funktionen nicht. Werfen Sie einen Blick eine der folgenden grundlegenden gegenseitige Rekursion Beispiel:

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)

Das ist etwas intuitiv und sehr deutlich gegenseitig rekursiv. Wenn ich jedoch jede Funktion auf, als eine innere Funktion wickeln, die einmal pro Anruf erstellt wird, wird es weniger klar:

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)

Ohne Berücksichtigung Optimierungen wie implizite memoization usw., ergibt sich eine Kette von Funktionsaufrufen, die nicht streng rekursiv ist, das Erstellen und verschiedene neue Funktionen aufrufen, ohne jemals zweimal das gleiche Aufruf. Dennoch folgen alle diese Funktionen eine gemeinsame Vorlage, und sind nur die gleiche Funktion erstellt immer und immer wieder (möglicherweise mit verschiedenen freien Variablen.

Und wieder können wir mit einem direkt äquivalent kommen (immerhin Klassen sind wirklich nur Schließungen, Recht;) Implementierungsklassen verwenden. Dies ist besonders wichtig, da diese Art von [insert name here] wird verwendet, zum Beispiel in der die Composite-Muster . Der Unterschied besteht darin, dass mit dem Composite-Entwurfsmuster, und die meisten Anwendungen (auch der Verschlüsse) werden die Instanzen der Regel nicht im laufenden Betrieb erstellt. Es ist nach wie vor im Wesentlichen gleich.

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)

Dieses Mal die Kette der Objekterstellung und Methodenaufrufe, aber das Prinzip ist das gleiche. (ich würde eigentlich beachten Sie, dass es etwas anders ist, dass Python eine einfache Wrapper auf einer pro-Objekt-Basis definiert, die sich die gleiche Funktion ruft jeder Zeit-- aber dies ist nicht unbedingt etwas, was wir wissen müssen, und es nicht für andere Implementierungen von Klassen und Objekten um wahr zu sein brauchen. Aber ja, streng darauf zu sprechen für beide Seiten rekursiv, sowie ... etwas mehr, und es ist, dass andere Sache, die ich will wissen.)

Answer 1

Wie Sie weisen darauf hin, ist dies immer noch gegenseitige Rekursion. Ich glaube nicht, das „etwas mehr“ Sie fragen, über einen Namen hat; wenn ja ich habe es noch nie gehört.

Answer 2

Die gegenseitige Rekursion ist nur ein Spezialfall von indirekter Rekursion .

Answer 3

Offenbar wird es genannt Mutual Rekursion :)

Der Artikel selbst gibt das gleiche Beispiel wie Sie, mit odd? und even? Funktionen.