Hola Habr! Les presento la traducción del artículo "Eliminando una recurrencia en Python, parte 1" de Eric Lippert.
En los últimos 20 años, he admirado la simplicidad y el poder de Python, aunque nunca he trabajado con él o estudiado en detalle.
Recientemente, lo he mirado de cerca, y resultó ser un lenguaje realmente agradable.
Una pregunta reciente sobre StackOverflow me hizo preguntarme cómo convertir un algoritmo recursivo en uno iterativo, y resultó que Python era un lenguaje bastante bueno para esto.
El problema que encontró el autor de la pregunta fue el siguiente:
- El jugador está en una celda arbitraria en un campo numerado;
- El objetivo es volver a la celda número 1;
- Si el jugador está en una casilla par, paga una moneda y va hasta la mitad de la celda No. 1;
- Si el jugador está en un cuadrado impar, puede pagar 5 monedas e ir directamente al primer cuadrado o pagar una moneda y dar un paso al cuadrado No. 1, en un cuadrado par.
La pregunta es: ¿cuál es la menor cantidad de monedas que debe pagar para regresar de la celda actual a la primera?
La tarea tiene una solución recursiva obvia:
def cost(s): if s <= 1: return 0 if s % 2 == 0: return 1 + cost(s // 2) return min(1 + cost(s - 1), 5)
Sin embargo, este programa se bloqueó, alcanzando la máxima profundidad de recursión, probablemente debido al hecho de que el autor de la pregunta experimentó con números muy grandes.
Por lo tanto, surge la pregunta: ¿cómo convertir un algoritmo recursivo en uno iterativo en Python?
Antes de comenzar, quiero señalar que, por supuesto, hay soluciones más rápidas para este problema específico, en sí mismo no es muy interesante.
Más bien, esta tarea sirvió solo como punto de partida en la cuestión de cómo, en el caso general, deshacerse de una sola llamada recursiva en un programa Python.
El punto es que puede convertir cualquier método recursivo simple y deshacerse de la recursividad, y este es solo un ejemplo que estaba a la mano.
La técnica que voy a mostrar, por supuesto, no coincide exactamente con la forma en que está escrito Python, probablemente una solución de estilo Python usaría generadores u otras características del lenguaje.
Lo que quiero mostrar aquí es cómo deshacerse de la recursividad utilizando una secuencia de transformaciones pequeñas y seguras, lo que lleva a la función a una forma en la que es fácil reemplazar la recursión con una iteración.
Para comenzar, veamos cómo llevar el programa a este formulario.
En el primer paso de nuestra conversión, quiero que los cálculos realizados antes de la llamada recursiva se reduzcan al cálculo del argumento, y los cálculos, después de la llamada recursiva, deben realizarse en un método separado que acepte el resultado de la llamada recursiva.
def add_one(n): return n + 1 def get_min(n): return min(n + 1, 5) def cost(s): if s <= 1: return 0 if s % 2 == 0: argument = s // 2 result = cost(argument) return add_one(result) argument = s - 1 result = cost(argument) return get_min(result)
El segundo paso que quiero hacer es el cálculo del argumento en una función separada:
En el tercer paso, quiero agregar una función auxiliar que seleccionará la función de continuación que se llama después de regresar de la recursividad.
Tenga en cuenta que la función auxiliar devuelve una función.
Ahora lo escribimos de forma más general y concisa:
Se puede ver que cada cambio realizado conserva el significado del programa.
Ahora la verificación de la paridad del número se realiza dos veces, aunque antes de los cambios había una verificación.
Si queremos, podemos resolver este problema combinando dos funciones auxiliares en una que devuelva una tupla.
Pero no nos preocupemos por esto como parte de esta tarea.
Hemos reducido nuestro método recursivo a la forma más general.
- En el caso base:
- calcular el valor a devolver;
- devuélvelo.
- En un caso no básico:
- calcular el argumento de recursividad;
- hacer una llamada recursiva;
- calcular el valor de retorno;
- devuélvelo.
Algo importante a lo que debe prestar atención en este paso es que after no debe contener cost llamadas de cost sí.
El método que muestro aquí elimina una sola llamada recursiva.
Si tiene 2 o más recurrencias, entonces necesitamos una solución diferente.
Una vez que hemos traído nuestro algoritmo recursivo a este formulario, ya es fácil convertirlo a iterativo.
El truco es imaginar lo que sucede en un programa recursivo.
Cómo hacemos un descenso recursivo: llamamos a get_argument antes de la llamada recursiva y llamamos a la función after después de regresar de la recursividad.
Es decir, todas las llamadas a get_argument ocurren antes de todas las llamadas a después .
Por lo tanto, podemos convertir esto en 2 ciclos: las primeras llamadas get_argument y forman una lista de funciones posteriores , y las segundas llamadas a todas las funciones posteriores :
¡No más recursión!
Parece magia, pero todo lo que hacemos aquí es lo mismo que la versión recursiva del programa, y en el mismo orden.
Este ejemplo refleja el pensamiento que a menudo repito sobre la pila de llamadas: su propósito es comunicar lo que sucederá a continuación, ¡y no lo que ya sucedió!
La única información útil sobre la pila de llamadas en la versión recursiva del programa es cuál es el valor posterior , ya que esta función se llama a continuación, y todo lo demás en la pila no es importante.
En lugar de usar la pila de llamadas como una forma ineficiente y engorrosa de almacenar la pila after , simplemente podemos almacenar la pila de funciones after .
La próxima vez veremos una forma más compleja de eliminar la recursividad en Python.