Ricorsione con resa

Question

Esiste un modo per mixare la ricorsione e la dichiarazione yield? Per esempio, un generatore di numeri infiniti (utilizzando la ricorsione) sarebbe qualcosa di simile:

def infinity(start): 
    yield start 
    # recursion here ... 

>>> it = infinity(1) 
>>> next(it) 
1 
>>> next(it) 
2 

ho provato:

def infinity(start): 
    yield start 
    infinity(start + 1) 

e

def infinity(start): 
    yield start 
    yield infinity(start + 1) 

Ma nessuno di loro ha fatto quello che voglio, il primo si è fermato dopo che ha prodotto start e il secondo ha prodotto start, quindi il generatore e quindi si è fermato.

NOTA: Si prega di, so che si può fare questo usando un ciclo while:

def infinity(start): 
    while True: 
     yield start 
     start += 1 

Voglio solo sapere se questo può essere fatto in modo ricorsivo.

Answer 1

Sì, si può fare questo:

def infinity(start): 
    yield start 
    for x in infinity(start + 1): 
     yield x 

Questo errore fuori una volta raggiunta la profondità massima di ricorsione, però.

A partire da Python 3.3, sarete in grado di utilizzare

def infinity(start): 
    yield start 
    yield from infinity(start + 1) 

Se basta chiamare la funzione del generatore in modo ricorsivo senza ciclo su esso o yield from -ing, tutto ciò che fai è costruire un nuovo generatore, senza effettivamente eseguire il corpo della funzione o cedere nulla.

Vedere PEP 380 per ulteriori dettagli.

Answer 2

In alcuni casi potrebbe essere preferibile utilizzare uno stack anziché la ricorsione per i generatori. Dovrebbe essere possibile riscrivere un metodo ricorsivo usando uno stack e un ciclo while.

Ecco un esempio di un metodo iterativo che utilizza un callback e può essere riscritta utilizzando la logica pila:

def traverse_tree(callback): 
    # Get the root node from somewhere. 
    root = get_root_node() 
    def recurse(node): 
     callback(node) 
     for child in node.get('children', []): 
      recurse(child) 
    recurse(root) 

Il metodo sopra attraversa un albero nodo in cui ogni nodo ha una matrice children che può contenere nodi figlio. Quando viene rilevato ogni nodo, viene richiamato il callback e il nodo corrente viene passato ad esso.

Il metodo potrebbe essere utilizzato in questo modo, stampando alcune proprietà su ciascun nodo.

def callback(node): 
    print(node['id']) 
traverse_tree(callback) 

Usare una pila al posto e scrivere il metodo di attraversamento come generatore

# A stack-based alternative to the traverse_tree method above. 
def iternodes(): 
    stack = [get_root_node()] 
    while stack: 
     node = stack.pop() 
     yield node 
     for child in node.get('children', []): 
      stack.append(child) 

Ora è possibile ottenere lo stesso comportamento di traverse_tree sopra, ma con un generatore:

for node in iternodes(): 
    print(node['id']) 

Questa non è una soluzione valida per tutti, ma per alcuni generatori potresti ottenere un risultato piacevole sostituendo l'elaborazione dello stack per ricorsivi sopra.

Answer 3

Quindi, in pratica, è sufficiente aggiungere un ciclo for a dove è necessario chiamare la funzione in modo ricorsivo. Questo vale per Python 2.7.