Recursión usando el rendimiento

¿Hay alguna manera de mezclar la recursividad y la declaración yield? Por ejemplo, un generador de números infinitos (usando recursión) sería algo como:

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

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

Lo intenté: 

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 yo quería, el primero se detuvo después de que dio start y el segundo dio start, luego el generador y luego se detuvo.

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

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

Solo quiero saber si esto se puede hacer recursivamente.

Author: juliomalegria, 2012-01-24
Source

3 answers

Sí, puedes hacer esto: 

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

Esto se producirá un error una vez que se alcance la profundidad de recursión máxima, sin embargo.

A partir de Python 3.3, podrás usar

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

Si simplemente llamas a tu función generadora recursivamente sin hacer un bucle sobre ella o yield from-ing, todo lo que haces es construir un nuevo generador, sin ejecutar realmente el cuerpo de la función o producir nada.

Véase PEP 380 para más detalles.

 101
Author: Sven Marnach,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-07-13 22:26:37

En algunos casos podría ser preferible usar una pila en lugar de la recursión para los generadores. Debería ser posible reescribir un método recursivo usando una pila y un bucle while.

Aquí hay un ejemplo de un método recursivo que usa 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 nodos donde cada nodo tiene una matriz children que puede contener nodos hijos. A medida que se encuentra cada nodo, se emite la devolución de llamada y se pasa el nodo actual a ella.

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

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

Use una pila en su lugar y escriba el método transversal como un 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 reversed(node.get('children', [])):
            stack.append(child)

(Tenga en cuenta que si desea el mismo orden transversal que originalmente, debe invertir el orden de los hijos porque el primer hijo agregado a la pila será el último que aparezca.)

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

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

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

 9
Author: t.888,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-06-18 13:19:51

Así que básicamente solo necesita agregar un bucle for en donde necesita llamar a su función recursivamente. Esto se aplica a Python 2.7.

 -2
Author: Bubble Bubble Bubble Gut,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-12-28 21:45:38