Che cosa è questo tipo di “ricorsione” mutuo chiamato?

Question

Il mio problema è con un certo stile di codice che assomiglia moltissimo la ricorsione, ma non è molto che. Ricorsione è, per citare Wikipedia ", viene applicato un metodo di funzioni che definiscono in cui essendo definita la funzione all'interno della sua propria definizione". Analogamente mutua ricorsione applica un'altra funzione che, applicato direttamente o indirettamente la funzione stiamo definendo.

Il problema è che il codice che sto pensando, e si occupano di, non usa la stessa funzione! Si utilizza lo stesso codice in un'altra funzione (come un metodo o chiusura).

Il problema qui è che, mentre il mio codice è lo stesso, le funzioni non sono. Date un'occhiata a Il seguente esempio di base reciproca ricorsione:

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)

Questo è piuttosto intuitivo, e molto chiaramente reciprocamente ricorsivo. Tuttavia, se mi avvolgo ogni funzione come una funzione interna che viene creato quando ogni chiamata, diventa meno chiaro:

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)

ottimizzazioni Ignorare le quali Memoizzazione implicita ecc, questo produce una catena di chiamate di funzione non strettamente ricorsiva, creando e chiamando vari nuove funzioni senza mai chiamare lo stesso due volte. Tuttavia tutte queste funzioni seguono un modello comune, e sono proprio la stessa funzione creato più e più volte (possibilmente con diverse variabili libere.

E ancora, siamo in grado di venire con un diretto equivalente (dopo tutto, le classi sono in realtà solo chiusure, a destra;) implementazione utilizzando le classi. Questo è particolarmente significativo, dal momento che questo stile di [inserire nome qui] è usato in, ad esempio, il Composite modello . La differenza è che con il design pattern Composite, e la maggior parte usi (anche delle chiusure), le istanze non sono in genere creati al volo. E 'ancora sostanzialmente la stessa.

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)

Questa volta la catena è di creazione di oggetti e chiamate di metodo, ma il principio è lo stesso. (vorrei davvero notare che è leggermente diverso, nel senso che Python definisce un semplice involucro su una base per-oggetto che si chiama la stessa funzione di ogni tempo--, ma questo non è necessariamente una cosa abbiamo bisogno di sapere, e non ha bisogno di essere vero per altre implementazioni di classi e oggetti. Ma sì, in senso stretto è reciprocamente ricorsivo, così come ... qualcosa di più, ed è l'altra cosa che voglio so.)

Answer 1

Come fai notare, questo è ancora mutua ricorsione. Non credo che il "di più" che stai chiedendo ha un nome; se lo fa non l'ho mai sentito.

Answer 2

ricorsione reciproca è solo un caso particolare di ricorsione indiretta .

Answer 3

A quanto pare, si chiama Mutual ricorsione :)

L'articolo fornisce anche lo stesso esempio di voi, con le funzioni di odd? e even?.