recursivos - recursividad python ejemplos

Recursión usando rendimiento

Question

¿Hay alguna manera de mezclar la recursividad y la declaración de yield ? Por ejemplo, un generador de números infinitos (usando recursividad) sería algo así 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 cedió el start y el segundo dio start , luego el generador y luego se detuvo.

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

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

Solo quiero saber si esto puede hacerse recursivamente.

Answer 1

En algunos casos, puede ser preferible utilizar una pila en lugar de recurrencia 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 usa una devolución de llamada y se puede reescribir utilizando la lógica de la 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 de elementos secundarios 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 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 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 niños porque el primer niño agregado a la pila será el último que se haya reventado).

Ahora puedes obtener el mismo comportamiento que el de 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 recursividad.

Answer 2

Entonces, básicamente, solo necesita agregar un bucle for en donde necesita llamar a su función recursivamente . Esto aplica para Python 2.7.

Answer 3

Sí, usted puede hacer esto:

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

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

A partir de Python 3.3, podrás usar

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

Si solo llama a su función de generador de forma recursiva sin pasar por encima de ella o yield from , todo lo que hace es construir un generador nuevo, sin ejecutar realmente el cuerpo de la función ni ceder nada.

Ver PEP 380 para más detalles.