Recursividad con rendimiento

Question

¿Hay alguna forma de mezclar recursividad y la instrucción yield? Por ejemplo, un generador de números infinitos (utilizando la recursividad) sería algo así como:

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

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

Traté:

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

y

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

Pero ninguno de ellos hizo lo que quiero, el primero se detuvo después de que cedió start y el segundo rindió start, luego el generador y luego se detuvo.

NOTA: Por favor, sé que puedes hacerlo usando un bucle while:

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

sólo quiero saber si esto se puede hacer de forma recursiva.

Answer 1

sí, se puede hacer esto:

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

Esto error una vez que se alcanza el nivel de recursividad, sin embargo.

A partir de Python 3.3, podrás utilizar

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

Si acaba de llamar a su función de generador de forma recursiva sin bucle sobre él o yield from -ing, todo lo que hacemos es construir un nuevo generador, sin ejecutar realmente el cuerpo de la función ni ceder nada.

Consulte PEP 380 para obtener más información.

Answer 2

En algunos casos, puede ser preferible utilizar una pila en lugar de recursividad para generadores. Debería ser posible reescribir un método recursivo utilizando una pila y un ciclo while.

Aquí hay un ejemplo de un método recursivo que utiliza una devolución de llamada y se puede reescribir usando la lógica de 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) 

El método anterior atraviesa un árbol de nodo en el que cada nodo tiene una matriz children que puede contener nodos secundarios. A medida que se encuentra cada nodo, se emite la devolución de llamada y se le pasa el nodo actual.

El método se podría usar de esta manera, imprimiendo alguna propiedad en cada nodo.

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

Utilice una pila en su lugar y escribir el método de recorrido como generador

# 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) 

Ahora usted puede conseguir el mismo comportamiento que traverse_tree anterior, pero con un generador:

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

Esta no es una solución única para todos, pero para algunos generadores puede obtener un buen resultado sustituyendo el procesamiento de pila por recursi en.

Answer 3

Básicamente, solo tiene que agregar un bucle for al donde necesita llamar a su función recursivamente. Esto aplica para Python 2.7.