python - ¿Pueden los generadores ser recursivos?

recursion generator

Question

Intenté ingenuamente crear un generador recursivo. No funcionó Esto es lo que hice:

def recursive_generator(lis):
    yield lis[0]
    recursive_generator(lis[1:])

for k in recursive_generator([6,3,9,1]):
    print(k)

Todo lo que obtuve fue el primer artículo 6 .

¿Hay alguna manera de hacer que ese código funcione? ¿Esencialmente transfiriendo el comando de yield al nivel anterior en un esquema de recursión?

Answer 1

¿Por qué su código no hizo el trabajo?

En su código, la función del generador:

1. devuelve (produce) el primer valor de la lista
2. luego crea un nuevo objeto iterador que llama a la misma función generadora y le pasa una porción de la lista
3. y luego se detiene

La segunda instancia del iterador, la creada recursivamente , nunca se repite. Es por eso que solo obtuviste el primer elemento de la lista.

Una función de generador es útil para crear automáticamente un objeto iterador (un objeto que implementa el protocolo iterador ), pero luego debe iterar sobre él: ya sea llamando manualmente al método next() en el objeto o mediante una declaración de bucle que usa automáticamente el protocolo iterador.

Entonces, ¿podemos llamar recursivamente a un generador?

La respuesta es si . Ahora, de vuelta a su código, si realmente desea hacer esto con una función de generador, supongo que podría intentar:

def recursive_generator(some_list):
    """
    Return some_list items, one at a time, recursively iterating over a slice of it... 
    """
    if len(some_list)>1:
    # some_list has more than one item, so iterate over it
        for i in recursive_generator(some_list[1:]):
            # recursively call this generator function to iterate over a slice of some_list.
            # return one item from the list.
            yield i
        else:
            # the iterator returned StopIteration, so the for loop is done.
            # to finish, return the only value not included in the slice we just iterated on.
            yield some_list[0]
    else:
        # some_list has only one item, no need to iterate on it.
        # just return the item.
        yield some_list[0]

some_list = [6,3,9,1]
for k in recursive_generator(some_list):
    print(k)

Nota: los artículos se devuelven en orden inverso, por lo que es posible que desee usar some_list.reverse() antes de llamar al generador la primera vez.

Lo importante a tener en cuenta en este ejemplo es: la función del generador se llama recursivamente en un bucle for , que ve un iterador y usa automáticamente el protocolo de iteración en él, por lo que en realidad obtiene valores de él.

Esto funciona, pero creo que esto realmente no es útil . Estamos utilizando una función de generador para iterar sobre una lista y simplemente sacar los elementos, uno a la vez, pero ... ¡una lista es iterable en sí misma, por lo que no se necesitan generadores! Por supuesto que lo entiendo, este es solo un ejemplo, tal vez hay aplicaciones útiles de esta idea.

Otro ejemplo

Reciclemos el ejemplo anterior (por pereza). Digamos que necesitamos imprimir los elementos en una lista, agregando a cada elemento el recuento de elementos anteriores (solo un ejemplo aleatorio, no necesariamente útil).

El código sería:

def recursive_generator(some_list):
    """
    Return some_list items, one at a time, recursively iterating over a slice of it...
    and adding to every item the count of previous items in the list
    """
    if len(some_list)>1:
    # some_list has more than one item, so iterate over it
        for i in recursive_generator(some_list[1:]):
            # recursively call this generator function to iterate over a slice of some_list.
            # return one item from the list, but add 1 first. 
            # Every recursive iteration will add 1, so we basically add the count of iterations.
            yield i + 1
        else:
            # the iterator returned StopIteration, so the for loop is done.
            # to finish, return the only value not included in the slice we just iterated on.
            yield some_list[0]
    else:
        # some_list has only one item, no need to iterate on it.
        # just return the item.
        yield some_list[0]

some_list = [6,3,9,1]
for k in recursive_generator(some_list):
    print(k)

Ahora, como puede ver, la función de generador está haciendo algo antes de devolver los elementos de la lista Y el uso de la recursividad comienza a tener sentido. Aún así, solo es un ejemplo estúpido, pero se entiende la idea.

Nota: por supuesto, en este estúpido ejemplo, se espera que la lista contenga solo números. Si realmente quieres intentarlo y romperlo, solo pon una cadena en some_list y diviértete. De nuevo, esto es solo un ejemplo, ¡no un código de producción !

Answer 2

Hasta Python 3.4, una función generadora solía generar StopIteration excepción StopIteration cuando se hace. Para el caso recursivo, otras excepciones (por ejemplo, IndexError ) se StopIteration antes que StopIteration , por lo tanto, lo agregamos manualmente.

def recursive_generator(lis):
    if not lis: raise StopIteration
    yield lis[0]
    yield from recursive_generator(lis[1:])

for k in recursive_generator([6, 3, 9, 1]):
    print(k)

def recursive_generator(lis):
    if not lis: raise StopIteration
    yield lis.pop(0)
    yield from recursive_generator(lis)

for k in recursive_generator([6, 3, 9, 1]):
    print(k)

Tenga en cuenta que for loop capturará la excepción StopIteration . Más sobre esto here

Answer 3

Los generadores recursivos son útiles para atravesar estructuras no lineales. Por ejemplo, deje que un árbol binario sea Ninguno o una tupla de valor, árbol izquierdo, árbol derecho. Un generador recursivo es la forma más fácil de visitar todos los nodos. Ejemplo:

tree = (0, (1, None, (2, (3, None, None), (4, (5, None, None), None))),
        (6, None, (7, (8, (9, None, None), None), None)))

def visit(tree):  # 
    if tree is not None:
        try:
            value, left, right = tree
        except ValueError:  # wrong number to unpack
            print("Bad tree:", tree)
        else:  # The following is one of 3 possible orders.
            yield from visit(left)
            yield value  # Put this first or last for different orders.
            yield from visit(right)

print(list(visit(tree)))

# prints nodes in the correct order for ''yield value'' in the middle.
# [1, 3, 2, 5, 4, 0, 6, 9, 8, 7]

Editar: reemplace if tree con if tree is not None para detectar otros valores falsos como errores.

Edición 2: acerca de poner las llamadas recursivas en la cláusula try: (comentario de @ jpmc26).

Para los nodos defectuosos, el código anterior solo registra el ValueError y continúa. Si, por ejemplo, (9,None,None) se reemplaza por (9,None) , la salida es

Bad tree: (9, None)
[1, 3, 2, 5, 4, 0, 6, 8, 7]

Más típico sería volver a subir después de iniciar sesión, haciendo que la salida sea

Bad tree: (9, None)
Traceback (most recent call last):
  File "F:/Python/a/tem4.py", line 16, in <module>
    print(list(visit(tree)))
  File "F:/Python/a/tem4.py", line 14, in visit
    yield from visit(right)
  File "F:/Python/a/tem4.py", line 14, in visit
    yield from visit(right)
  File "F:/Python/a/tem4.py", line 12, in visit
    yield from visit(left)
  File "F:/Python/a/tem4.py", line 12, in visit
    yield from visit(left)
  File "F:/Python/a/tem4.py", line 7, in visit
    value, left, right = tree
ValueError: not enough values to unpack (expected 3, got 2)

El rastreo proporciona la ruta desde la raíz hasta el nodo defectuoso. Se podría ajustar la llamada de visit(tree) para reducir el rastreo a la ruta: (raíz, derecha, derecha, izquierda, izquierda).

Si las llamadas recursivas se incluyen en la cláusula try:, el error se recupera, se vuelve a registrar y se vuelve a generar en cada nivel del árbol.

Bad tree: (9, None)
Bad tree: (8, (9, None), None)
Bad tree: (7, (8, (9, None), None), None)
Bad tree: (6, None, (7, (8, (9, None), None), None))
Bad tree: (0, (1, None, (2, (3, None, None), (4, (5, None, None), None))), (6, None, (7, (8, (9, None), None), None)))
Traceback (most recent call last):
...  # same as before

Los informes de registro múltiple son probablemente más ruido que ayuda. Si uno desea la ruta al nodo defectuoso, podría ser más fácil ajustar cada llamada recursiva en su propio intento: cláusula y elevar un nuevo ValueError en cada nivel, con la ruta construida hasta el momento.

Conclusión: si no se está utilizando una excepción para el control de flujo (como se puede hacer con IndexError, por ejemplo), la presencia y las ubicaciones de las declaraciones try: dependen del informe de errores que se desee.

Answer 4

Prueba esto:

def recursive_generator(lis):
    yield lis[0]
    yield from recursive_generator(lis[1:])

for k in recursive_generator([6,3,9,1]):
    print(k)

Debo señalar que esto no funciona debido a un error en su función. Probablemente debería incluir una verificación de que lis no está vacío, como se muestra a continuación:

def recursive_generator(lis):
    if lis:
        yield lis[0]
        yield from recursive_generator(lis[1:])

En caso de que esté en Python 2.7 y no tenga yield from , consulte esta pregunta.

Answer 5

Sí, puedes tener generadores recursivos. Sin embargo, sufren el mismo límite de profundidad de recursión que otras funciones recursivas.

def recurse(x):
  yield x
  yield from recurse(x)

for (i, x) in enumerate(recurse(5)):
  print(i, x)

Este ciclo llega a aproximadamente 3000 (para mí) antes de fallar.

Sin embargo, con algunos trucos, puede crear una función que alimente un generador a sí mismo. Esto le permite escribir generadores como si fueran recursivos pero no lo son: https://gist.github.com/3noch/7969f416d403ba3a54a788b113c204ce