algorithm - recursivas - recursividad de cola ejemplos
¿Se pueden volver a escribir todas las funciones recursivas como recursivas de cola? (7)
No, se puede hacer "naturalmente" solo para llamadas con una llamada recursiva. Para dos o más llamadas recursivas, puede, por supuesto, imitar el marco de la pila usted mismo. Pero será muy feo y no será recursivo en la cola, en el sentido de optimizar la memoria.
El punto con recursividad de cola es que no quieres volver a la pila de padres. Simplemente transfiera esa información a la pila secundaria, que puede reemplazar por completo la pila padre, en lugar de crecer la pila.
Posible duplicado:
¿Hay problemas que no se pueden escribir usando la recursividad de cola?
Desde mi punto de vista, la recursividad de cola es una optimización que puede usar cuando una llamada recursiva no necesita información de las llamadas recursivas que va a enviar correo no deseado.
¿Es posible entonces implementar todas las funciones recursivas usando recursividad de cola? ¿Qué tal algo como DFS, donde necesitas que el niño más interno regrese antes que el padre?
El algoritmo recursivo es un algoritmo que se implementó de acuerdo con la estrategia Divide & Conquer, donde resolver cada subproblema intermedio produce 0, 1 o más subproblemas nuevos más pequeños. Si estos sub-problemas se resuelven en orden LIFO, obtienes un algoritmo recursivo clásico.
Ahora, si se sabe que su algoritmo produce solo 0 o 1 sub-problema en cada paso, entonces este algoritmo puede implementarse fácilmente a través de la recursividad de cola. De hecho, dicho algoritmo se puede reescribir fácilmente como un algoritmo iterativo y se puede implementar mediante un ciclo simple. (No es necesario agregar, la recursividad de cola es solo otra forma menos explícita de implementar la iteración).
Un ejemplo de libro de escuela de dicho algoritmo recursivo sería el enfoque recursivo para el cálculo factorial: calcular n! ¡necesitas calcular (n-1)! primero, es decir, en cada paso recursivo solo se descubre un sub-problema más pequeño. Esta es la propiedad que hace que sea tan fácil convertir el algoritmo de cálculo factorial en uno realmente iterativo (o recursivo).
Sin embargo, si sabe que, en general, el número de sub-problemas generados en cada paso de su algoritmo es más de 1, entonces su algoritmo es sustancialmente recursivo. No puede ser reescrito como algoritmo iterativo, no puede ser implementado a través de recursividad de cola. Cualquier intento de implementar dicho algoritmo en forma iterativa o recursiva de cola requerirá almacenamiento LIFO adicional de tamaño no constante para almacenar subproblemas "pendientes". Tales intentos de implementación simplemente ofuscarían la naturaleza recursiva inevitable del algoritmo implementando la recursión manualmente .
Por ejemplo, un problema tan simple como el cruce de un árbol binario con enlaces padre-> hijo (y sin enlaces hijo-> padres) es un problema sustancialmente recursivo. No se puede hacer mediante algoritmo recursivo de cola, no se puede hacer mediante un algoritmo iterativo.
No sé si todas las funciones recursivas se pueden volver a escribir para recursivas de cola, pero muchas de ellas sí. Un método estándar para hacer esto es usar un acumulador. Por ejemplo, la función factorial se puede escribir (en Common Lisp) así:
(defun factorial (n)
(if (<= n 1)
1
(* n (factorial (1- n)))))
Esto es recursivo, pero no recursivo de cola. Puede ser recursivo de cola agregando un argumento de acumulador:
(defun factorial-accum (accum n)
(if (<= n 1)
accum
(factorial-accum (* n accum) (1- n))))
Los factoriales pueden calcularse configurando el acumulador en 1. Por ejemplo, el factorial de 3 es:
(factorial-accum 1 3)
Sin embargo, para mí no es claro si todas las funciones recursivas pueden reescribirse como funciones recursivas de cola usando métodos como este. Pero ciertamente muchas funciones pueden serlo.
Todos los programas pueden reescribirse como llamadas finales usando el pase de continuación. Simplemente agregue un parámetro a la llamada final que represente la continuación de la ejecución actual.
Cualquier lenguaje completo de Turning realiza la misma transformación que proporciona el paso de continuación: crea un número de Gödel para el programa y parámetros de entrada a los que retorna la llamada que no es de cola, y pasa eso como un parámetro a la llamada final, aunque obviamente los entornos donde esto es hecho para ti con una continuación, co-rutina u otra construcción de primera clase lo hace mucho más fácil.
CPS se utiliza como una optimización de compilador y he escrito intérpretes previamente utilizando el paso de continuación. El lenguaje de programación del esquema está diseñado para permitir que se implemente de tal manera con los requisitos en el estándar para la optimización de la cola de llamadas y las continuaciones de primera clase.
Sí tu puedes. La transformación generalmente implica el mantenimiento explícito de la información necesaria, que de otro modo se mantendría para nosotros distribuida implícitamente entre los marcos de llamadas de la pila de ejecución durante el tiempo de ejecución.
Tan sencillo como eso. Independientemente de lo que el sistema de tiempo de ejecución haga durante la ejecución implícitamente, podemos hacerlo de manera explícita. No hay gran misterio aquí. Las computadoras están hechas de silicio y cobre y acero.
Es trivial implementar DFS como un bucle con cola explícita de estados / posiciones / nodos para procesar. De hecho, se define de esa manera: DFS reemplaza la primera entrada revelada en la cola con todos los arcos que provienen de ella; BFS agrega estos arcos al final de la cola.
La transformación de estilo de continuación de paso deja todas las llamadas de función en un programa como llamadas de cola después de que se realiza. Este es un hecho simple de la vida. Las continuaciones utilizadas crecerán y disminuirán, pero las llamadas serán todas llamadas de cola.
Podemos además reificar el estado de propagación del proceso en continuaciones, como datos mantenidos explícitamente en el montón. Lo que esto logra al final es la explicación y la reificación, mover las cosas implícitas en la pila a las cosas explícitas que viven en el montón, simplificando y desmitificando el flujo de control.
Si y no.
Sí, utilizado junto con otros mecanismos de flujo de control (por ejemplo, el paso de continuación) puede expresar cualquier flujo de control arbitrario como recursión final.
No, no es posible expresar todas las recursiones como recursividad de cola a menos que complemente la recursión de cola con otros mecanismos de flujo de control.
Depende de exactamente lo que estás preguntando.
Si desea mantener todas las funciones como funciones (sin estado mutable) con las mismas firmas, entonces no. El ejemplo más obvio es el quicksort, donde ambas llamadas no pueden ser llamadas de cola.
Si puede modificar la función de varias maneras, entonces sí. A veces, una modificación local es suficiente; a menudo puede agregar un "acumulador" que construye alguna expresión que se devuelve, aunque, si el resultado involucra operaciones no conmutativas, entonces debe tener cuidado (por ejemplo, cuando ingenuamente construye listas enlazadas, el orden se invierte) o puede agregar una pila.
Alternativamente, puede hacer una modificación global de todo el programa, en el que cada función toma como argumento adicional la función que contiene acciones futuras. Esta es la continuación que pasa de lo que Pete está hablando .
si trabajas a mano, la modificación local suele ser bastante fácil. pero si está haciendo una reescritura automática (en un compilador, por ejemplo), entonces es más sencillo adoptar el enfoque global (requiere menos "inteligencia").