6

Encontré este código que usa recursividad y yield pero no logro entender la lógica de como funciona yield para imprimir el par (num, num) y de por qué dos veces pone yield h en dos bucles distintos.

def hanoi(n, src, dst, tmp):
    if n <= 0:
        pass
    else:
        for h in hanoi(n-1, src, tmp, dst):
            yield h
        yield (src, dst)
        for h in hanoi(n-1, tmp, dst, src):
            yield h
1
  • 4
    Hola Mauricio. Bienvenido. ¡Muy interesante pregunta pero la explicación es larga, e involucra bastantes conceptos! Espero que mi respuesta sea clara. Puedes pedir en comentarios cualquier aclaración adicional que precises.
    – abulafia
    el 21 sep. 2018 a las 7:58

1 respuesta 1

12

yield y generadores

La instrucción yield es una especie de return, pero a diferencia de este último no da por terminada la función, sino que puede reanudarse después en la línea siguiente a donde haya ocurrido yield.

Esto puede usarse para objetivos diversos (por ejemplo, para implementar la idea de "corutina" y posibilitar que varias tareas avancen a la vez "por turnos", pasando el turno de una a otra con el yield). O, más frecuentemente y como es tu caso, para implementar generadores.

Cuando una función incluye la sentencia yield, python la trata de forma especial. En el momento que "ejecutas" la función, en realidad no se ejecuta nada, sino que se crea un generador, que es un tipo especial de objeto. Puedes guardar ese objeto en una variable y posteriormente, cada vez que hagas next() sobre ese objeto, el código de la rutina se ejecutará hasta llegar al siguiente yield y allí se pausará. El valor especificado tras yield será lo que retorne next().

Un mínimo ejemplo puede aclarar las cosas:

def ejemplo():
   a = 0
   yield a
   a += 1
   yield a

g = ejemplo()
# No se ejecuta nada aún, g es un generador
r = next(g)  # r vale 0

Al ejecutar ejemplo(), la función no se ejecuta, pero se crea el objeto generador que nuestro programa recoge en la variable g. Al hacer next(g) se ejecuta la función, guarda un 0 en a y hace yield a, lo que causa que next(g) termine retornando 0 (que era el valor de a). Pero la rutina puede ser reanudada. Si hacemos de nuevo next(g) continuará en la línea siguiente, hará a+=1 y el siguiente yield a "retornará" un 1, que será el valor retornado por ese next(g).

¿Qué pasa si hacemos next(g) una vez más? En ese caso la rutina se reanuda en la línea siguiente al último yield, y como ya no hay más líneas, terminará. En este caso la terminación contiene un return None implícito, como todas las funciones python, que retornan None cuando alcanzan su final. Pero este None no ha sido retornado por un yield, sino por un return normal (aunque implícito).

Esto es detectado por Python. Cuando un generador retorna con un return normal en vez de yield, python genera la excepción StopIteration y a partir de ese momento ya no tiene sentido hacer más next(g), pues se generará siempre esa excepción que señala que el generador ha terminado. Así:

>>> g = ejemplo()
>>> next(g)
0
>>> next(g)
1
>>> next(g)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Generadores y bucles for

Todo lo anterior lo "hace invisible" python si lo usas en un bucle for, pues internamente lo que hace python es crear el generador y llamar a next() repetidas veces (una para cada iteración del for), hasta que se produzca StopIteration en cuyo caso abandona el bucle.

Por tanto puedes hacer:

for r in ejemplo():
   print(r)

Y saldría 0, 1 y terminaría.

Hanoi y recursividad

En tu caso el yield se complica con la recursividad, lo que hace bastante difícil de leer y entender ese código.

La función hanoi(), ya que contiene instrucciones yield, no es una función normal. Cuando la ejecutes dentro de un programa, por ejemplo así:

hanoi(5, 1, 2, 3)

no verías nada. No se ejecuta realmente sino que se crearía el generador. Tendrías que ir haciendo next() sobre él para que la ejecución tuviera lugar. O también puedes ejecutarlo como parte de un for, así:

for movimiento in hanoi(5, 1, 2, 3):
    print(movimiento)

En ese caso, como ya explicamos, la maquinaria del for crea el generador y va haciendo next() sobre él, almacenando en la variable movimiento los sucesivos valores que next() vaya retornando, que me limito a imprimir.

Entonces, en el primer next() comenzaría la ejecución del generador, que comenzará mirando si n es 0 (si lo fuera, no hace nada, con lo que se produce el fin de ejecución del generador, un return None implícito, una excepción StopIteration y el final del for).

Si no es el caso, se entra en el else, que usa recursividad para resolver el problema. La recursividad en este caso parte de la idea de que mover una torre con N discos de src a dst puede resolverse moviendo primero los N-1 discos superiores desde src a tmp, después el disco que queda de src a dst y por último volviendo a mover los N-1 discos de tmp a dst.

Para hacer el movimiento de los N-1 discos llama de nuevo a hanoi(). El que funcione eso es fuente inagotable de maravilla, y la magia de la recursividad.

En esta implementación concreta para invocar a hanoi() de forma recursiva, ya que no es una función normal sino un generador, lo hacemos de nuevo dentro de bucles for. Iteramos sobre los movimientos que produce hanoi() para el problema N-1, y cada uno de esos movimientos (guardado en h) lo "retornamos" a su vez al bucle principal haciendo yield h. Cada una de estas h será una tupla (¿por qué? sigue leyendo)

Una vez "retornados" los movimientos para los N-1 discos iniciales, hacemos yield (src, dst) y aqui es donde retornamos la tupla que mueve un solo disco. En el bucle for que hicimos antes, la llamada recursiva a hanoi() producirá a su vez más llamadas recursivas, hasta que eventualmente se alcanzará un momento en que n sea 1, es decir, haya que mover un solo disco. En ese caso n-1 vale cero, por lo que ninguno de los bucles for que hay dentro llega a ejecutarse (todos terminan antes de iterar porque el primer next() eleva StopIteration). Así que para el caso n=1 el único yield que llega a ejecutars es el yield (src,dst), que indica como mover (trivialmente) un solo disco de src a dst.

El siguiente for funciona de modo análogo para mover los N-1 discos que estaban en la aguja tmp de nuevo a la aguja dst.

Para rematar: yield from

En Python 3 se añade la sintaxis yield from, que permite a un generador "delegar" su trabajo en otro generador.

Es decir, si dentro de un generador tienes:

yield from sub_generador()

entonces python conectará tu generador con el subgenerador, de modo que todos los yield que haga el subgenerador es como si los hubiera hecho el tuyo. Cuando el sub-generador se agote (eleve StopIteration) el yield from se dará por terminado y se seguirá por la línea siguiente. Es como si en el generador principal hubieras puesto:

for valor in sub_generador():
    yield valor

¡Un momento! ¿No es esto lo que tenemos precisamente dentro de la función hanoi() (aunque en este caso y debido a la magia de la recursividad el subgenerador es de nuevo la misma función).

Eso implica que podemos reescribirlo así:

def hanoi(n, src, dst, tmp):
    if n <= 0:
        pass
    else:
        yield from hanoi(n-1, src, tmp, dst)
        yield (src, dst)
        yield from hanoi(n-1, tmp, dst, src)

Esta sintaxis, si no más clara (que en mi opinión lo es), al menos es más corta.

1
  • se puede decir que los generadores son como cursores donde tienen atributos especiales para iterar el 21 sep. 2018 a las 11:36

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.