¿Qué es la cola de la recursión?
https://stackoverflow.com/questions/33923
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Mientras comienzan a aprender lisp, me he encontrado con el término cola-recursiva.¿Qué significa exactamente?
Solución
Considere una función simple que agrega los N primeros números enteros.(por ejemplo, sum(5) = 1 + 2 + 3 + 4 + 5 = 15).
Aquí es un simple JavaScript en la aplicación que utiliza la recursividad:
function recsum(x) {
if (x===1) {
return x;
} else {
return x + recsum(x-1);
}
}
Si usted llama recsum(5), esto es lo que la intérprete de JavaScript para evaluar:
recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
15
Observe cómo cada llamada recursiva tiene que completar antes de que el intérprete de JavaScript comienza a hacer el trabajo de calcular la suma.
He aquí un cola-versión recursiva de la misma función:
function tailrecsum(x, running_total=0) {
if (x===0) {
return running_total;
} else {
return tailrecsum(x-1, running_total+x);
}
}
Aquí está la secuencia de eventos que ocurrirían si usted llama tailrecsum(5), (que efectivamente podría ser tailrecsum(5, 0), debido a la omisión segundo argumento).
tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15
En la cola de la recursivo caso, con cada evaluación de la llamada recursiva, el running_total se actualiza.
Nota:La respuesta original utilizado ejemplos de Python.Estos han sido cambiados para JavaScript, ya que los modernos intérpretes de JavaScript apoyo cola de llamadas de optimización pero Python intérpretes no.
Otros consejos
En tradicional de la recursividad, el modelo típico es que usted realice sus llamadas recursivas en primer lugar, y luego de tomar el valor de retorno de la llamada recursiva y calcular el resultado.De esta manera, usted no recibe el resultado de su cálculo hasta que usted ha regresado de cada llamada recursiva.
En la recursividad de cola, usted realizar sus cálculos en primer lugar, y, a continuación, ejecutar la llamada recursiva, pasando por los resultados de su actual paso al siguiente paso recursivo.Esto se traduce en la última instrucción que está en la forma de (return (recursive-function params)). Básicamente, el valor de retorno de cualquier paso recursivo es el mismo que el valor de retorno de la siguiente llamada recursiva.
La consecuencia de esto es que una vez que esté listo para realizar su siguiente paso recursivo, no es necesario el marco de pila actual más.Esto permite la optimización.De hecho, adecuadamente con un compilador escrito, usted debe nunca tener un desbordamiento de pila se rien con una cola de llamadas recursivas.Simplemente reutilizar el marco de pila actual para el siguiente paso recursivo.Estoy bastante seguro de Lisp hace esto.
Un punto importante es que la cola de la recursividad es esencialmente equivalente a un bucle.No es sólo una cuestión de optimización del compilador, pero un hecho fundamental acerca de la expresividad.Esto va en ambos sentidos:usted puede tomar cualquier bucle de la forma
while(E) { S }; return Q
donde E y Q son expresiones y S es una secuencia de instrucciones, y convertirlo en una cola de función recursiva
f() = if E then { S; return f() } else { return Q }
Por supuesto, E, S, y Q tienen que ser definidos para calcular algunos valores interesante sobre algunas variables.Por ejemplo, el bucle de la función
sum(n) {
int i = 1, k = 0;
while( i <= n ) {
k += i;
++i;
}
return k;
}
es equivalente a la cola de la función recursiva(s)
sum_aux(n,i,k) {
if( i <= n ) {
return sum_aux(n,i+1,k+i);
} else {
return k;
}
}
sum(n) {
return sum_aux(n,1,0);
}
(Esta "envoltura" de la cola de la función recursiva de una función con el menor número de parámetros es un funcional común idioma.)
Este extracto del libro Programación en Lua muestra cómo hacer una adecuada recursión de la cola (en Lua, pero debe aplicarse a Lisp demasiado) y por qué es mejor.
Un cola de llamadas [cola de recursividad] es una especie de ir vestida como una llamada.Una cola de llamadas que sucede cuando una la función llama a otra como su última la acción, así que no tiene nada más que hacer.Por ejemplo, en el código siguiente, la llamada a
ges una cola de llamadas:function f (x) return g(x) endDespués de
fllamadasg, no tiene nada más a hacer.En tales situaciones, el programa de no es necesario volver a la llamada la función cuando la función llamada los extremos.Por lo tanto, después de la cola de llamadas, el programa no necesita mantener información acerca de la función de llamada en la pila....Debido a que una adecuada cola de llamadas no utiliza el espacio de la pila, no hay límite en el número de "anidada" cola de llamadas que un el programa puede hacer.Por ejemplo, podemos llamar a la siguiente función con cualquier número como argumento;nunca desbordamiento de la pila:
function foo (n) if n > 0 then return foo(n - 1) end end...Como he dicho antes, una cola de llamadas es un tipo de goto.Como tal, una muy útil la aplicación adecuada de la cola de llamadas en Lua es para la programación de máquinas de estado.Tales aplicaciones pueden representar cada una de las el estado a través de una función;para cambiar el estado de es ir a (o llamar) una específica la función.Como ejemplo, vamos nosotros considere la posibilidad de un simple juego de laberinto.El laberinto tiene varias habitaciones, cada una con hasta cuatro puertas:norte, sur, este, y oeste.En cada paso, el usuario entra en un la dirección del movimiento.Si hay una puerta en ese sentido, el usuario va a la correspondiente sala;de lo contrario, el programa imprime un mensaje de advertencia.El objetivo es para ir de un cuarto a un final de la sala.
Este juego es un típico estado de la máquina, donde el ambiente actual es el estado.Podemos implementar el laberinto con una función para cada habitación.Utilizamos cola las llamadas a mover de una habitación a otro.Un pequeño laberinto con cuatro habitaciones podría parecer a esto:
function room1 () local move = io.read() if move == "south" then return room3() elseif move == "east" then return room2() else print("invalid move") return room1() -- stay in the same room end end function room2 () local move = io.read() if move == "south" then return room4() elseif move == "west" then return room1() else print("invalid move") return room2() end end function room3 () local move = io.read() if move == "north" then return room1() elseif move == "east" then return room4() else print("invalid move") return room3() end end function room4 () print("congratulations!") end
Así que usted ve, cuando usted hace una llamada recursiva como:
function x(n)
if n==0 then return 0
n= n-2
return x(n) + 1
end
Esta no es la cola recursiva, ya que todavía tiene cosas que hacer (agregar 1) en que la función después de la llamada recursiva se hace.Si la entrada de un número muy alto es probable causar un desbordamiento de pila.
El uso regular de la recursividad, cada llamada recursiva empuja a otra entrada en la pila de llamadas.Cuando la recursividad es completado, la aplicación se ha pop cada entrada fuera de todo el camino de vuelta hacia abajo.
Con la cola de la recursividad, dependiendo del idioma, el compilador puede ser capaz de colapso de la pila hacia abajo para una entrada, para ahorrar espacio en la pila...Una gran consulta recursiva puede causar un desbordamiento de pila.
Básicamente Cola recursiones son capaces de ser optimizados en la iteración.
En lugar de explicar con palabras, he aquí un ejemplo.Este es un Esquema de la versión de la función factorial:
(define (factorial x)
(if (= x 0) 1
(* x (factorial (- x 1)))))
Aquí hay una versión de factorial que es cola-recursiva:
(define factorial
(letrec ((fact (lambda (x accum)
(if (= x 0) accum
(fact (- x 1) (* accum x))))))
(lambda (x)
(fact x 1))))
Usted notará que en la primera versión que la llamada recursiva al hecho de que es alimentado en la multiplicación de expresión, y por lo tanto el estado tiene que ser guardado en la pila al hacer la llamada recursiva.En la cola de la versión recursiva no hay otra expresión de espera para el valor de la llamada recursiva, y ya no hay más trabajo que hacer, el estado no tiene que ser guardado en la pila.Como regla general, el Esquema de la cola-funciones recursivas uso constante de espacio de pila.
El archivo de jerga que tiene esto que decir acerca de la definición de la cola de la recursividad:
la recursividad de cola /n./
Si usted no está enfermo de lo que ya, de ver la cola de la recursividad.
La cola de recursividad se refiere a la llamada recursiva ser la última en la última instrucción de lógica en el algoritmo recursivo.
Normalmente en la recursividad, tiene un caso base que es lo que detiene las llamadas recursivas y comienza a estallar la pila de llamadas.Para usar un ejemplo clásico, aunque más C-ish de Lisp, la función factorial muestra la cola de la recursividad.La llamada recursiva se produce después de la comprobación de la base de la condición.
factorial(x, fac=1) {
if (x == 1)
return fac;
else
return factorial(x-1, x*fac);
}
La primera llamada a factorial sería factorial(n) donde fac=1 (valor predeterminado) y n es el número para el que el factorial se calcula.
Esto significa que en lugar de tener que empujar el puntero de instrucción en la pila, usted puede simplemente saltar a la parte superior de una función recursiva y continuar la ejecución.Esto permite funciones para que se llame a sí misma indefinidamente sin desbordar la pila.
Escribí un blog post sobre el tema, que tiene ejemplos gráficos de lo que los marcos de pila aspecto.
Este es un fragmento de código de la comparación de dos funciones.La primera es la tradicional, la recursividad para encontrar el factorial de un número dado.El segundo utiliza la cola de la recursividad.
Muy intuitiva y simple de entender.
Una manera fácil de saber si una función recursiva es una cola recursiva es si devuelve un valor concreto en el caso base.Lo que significa que no devuelve 1 o verdadero, o algo como eso.Es más que probable retorno alguna variante de uno de los parámetros del método.
Otra manera es decir es si la llamada recursiva es libre de cualquier adición, la aritmética, la modificación, etc...El significado no es más que una pura llamada recursiva.
public static int factorial(int mynumber) {
if (mynumber == 1) {
return 1;
} else {
return mynumber * factorial(--mynumber);
}
}
public static int tail_factorial(int mynumber, int sofar) {
if (mynumber == 1) {
return sofar;
} else {
return tail_factorial(--mynumber, sofar * mynumber);
}
}
La mejor manera de entender para mí tail call recursion es un caso especial de la recursividad donde el última llamada(o de la cola de llamadas) es la función en sí.
La comparación de los ejemplos proporcionados en Python:
def recsum(x):
if x == 1:
return x
else:
return x + recsum(x - 1)
^La RECURSIVIDAD
def tailrecsum(x, running_total=0):
if x == 0:
return running_total
else:
return tailrecsum(x - 1, running_total + x)
^RECURSIÓN DE LA COLA
Como se puede ver en la general recursiva versión, la última en el bloque de código es x + recsum(x - 1).Así que después de llamar a la recsum método, no hay otra operación que se x + ...
Sin embargo, en la cola de la versión recursiva, el final de la llamada(o la cola de llamadas) en el bloque de código es tailrecsum(x - 1, running_total + x) lo que significa que la última llamada al método en sí y no a la operación después de que.
Este punto es importante porque la cola de la recursividad como se ve aquí no es hacer la memoria de crecer, porque cuando el subyacente VM ve a una función se llama a sí mismo en una posición de la cola (la última expresión se evalúa en una función), se elimina el marco de pila actual, lo que se conoce como Cola de llamadas de Optimización(TCO).
EDITAR
NB.Tened en cuenta que el ejemplo anterior está escrito en Python cuyo tiempo de ejecución no admite la TCO.Este es sólo un ejemplo para explicar el punto.El TCO es compatible en idiomas como el Esquema, Haskell, etc
En Java, he aquí una posible cola implementación recursiva de la función de Fibonacci:
public int tailRecursive(final int n) {
if (n <= 2)
return 1;
return tailRecursiveAux(n, 1, 1);
}
private int tailRecursiveAux(int n, int iter, int acc) {
if (iter == n)
return acc;
return tailRecursiveAux(n, ++iter, acc + iter);
}
Esto contrasta con el estándar de implementación recursiva:
public int recursive(final int n) {
if (n <= 2)
return 1;
return recursive(n - 1) + recursive(n - 2);
}
Aquí es un Common Lisp ejemplo que hace factoriales utilizando la cola de la recursividad.Debido a la pila de-menos de la naturaleza, se podría realizar increíblemente grande factorial cálculos ...
(defun ! (n &optional (product 1))
(if (zerop n) product
(! (1- n) (* product n))))
Y, a continuación, para la diversión que usted puede intentar (format nil "~R" (! 25))
Yo no soy un Lisp programador, pero creo que este será de ayuda.
Básicamente, es un estilo de programación que la llamada recursiva es la última cosa que haga.
En definitiva, una recursión de la cola tiene la llamada recursiva como la última declaración de la función, de modo que no tiene que esperar a que la llamada recursiva.
Así que esta es una cola de recursividad es decir,N(x - 1, p * x) es la última instrucción en la función donde el compilador es inteligente para darse cuenta de que puede ser optimizado para una for-loop (factorial).El segundo parámetro p lleva el producto intermedio valor.
function N(x, p) {
return x == 1 ? p : N(x - 1, p * x);
}
Esta no es la cola recursivos en el camino de la escritura por encima de la función factorial (aunque algunos compiladores de C++ pueden ser capaces de optimizar todos modos).
function N(x) {
return x == 1 ? 1 : x * N(x - 1);
}
pero esto no es:
function F(x) {
if (x == 1) return 0;
if (x == 2) return 1;
return F(x - 1) + F(x - 2);
}
Me hizo escribir un largo post titulado "La Comprensión De La Cola De Recursividad – Visual Studio C++ – Asamblea Vista"
aquí es un Perl versión 5 de la tailrecsum la función se mencionó anteriormente.
sub tail_rec_sum($;$){
my( $x,$running_total ) = (@_,0);
return $running_total unless $x;
@_ = ($x-1,$running_total+$x);
goto &tail_rec_sum; # throw away current stack frame
}
Este es un extracto de Estructura e Interpretación de los Programas de Ordenador acerca de las copias de la recursividad.
En el contraste de la iteración y recursión, debemos tener cuidado de no confundir la noción de un proceso recursivo con la noción de un procedimiento recursivo.Cuando se describe un procedimiento recursivo, estamos refiriéndose a la sintáctica hecho de que la definición del procedimiento se refiere (directa o indirectamente) para el procedimiento en sí.Pero cuando nos describir un proceso como siguiendo un patrón que es, digamos, linealmente recursiva, estamos hablando de cómo evoluciona el proceso, no se trata de la sintaxis de cómo un procedimiento escrito.Puede parecer preocupante el hecho de que nos referimos a un procedimiento recursivo como el iter como la generación de una proceso iterativo.Sin embargo, el proceso es iterativo:Su estado es capturado por completo con sus tres variables de estado, y un intérprete necesidad de mantener un seguimiento de sólo tres variables con el fin de ejecutar el proceso.
Una razón por la que la distinción entre proceso y procedimiento puede ser confuso es que la mayoría de las implementaciones de lenguajes comunes (incluyendo Ada, Pascal, y C) están diseñados de tal manera que la interpretación de cualquier recursiva procedimiento consume una cantidad de memoria que crece con el número de procedimiento de llamadas, incluso cuando el proceso descrito es, en principio, iterativo.Como consecuencia, estos lenguajes pueden describir iterativo los procesos sólo recurriendo a propósito especial "bucles" como hacer, repito, hasta, para, y mientras. La aplicación de Esquema no comparte este defecto.Es se ejecutará un proceso iterativo en el espacio continuo, incluso si la proceso iterativo se describe mediante un procedimiento recursivo.Un aplicación con esta propiedad se llama cola-recursiva. Con un cola-recursivas aplicación, la iteración puede ser expresado mediante el procedimiento ordinario llamar mecanismo, por lo que especial iteración las construcciones son útiles sólo como azúcar sintáctico.
La cola de la recursividad es la vida que están viviendo ahora.Usted constantemente reciclar el mismo marco de pila, más y más, porque no hay ninguna razón o medios para regresar a una "previa" de marco.El pasado, pasado está y hace con lo que puede ser descartado.Usted obtiene un marco para siempre en movimiento hacia el futuro, hasta que su proceso inevitablemente muere.
La analogía al considerar algunos procesos pueden utilizar marcos adicionales, pero todavía se consideran cola-recursivo si la pila no crecer infinitamente.
Una cola de recursividad es una función recursiva, donde la función de llamadas sí al final ("cola") de la función en la que ningún cálculo se después de hecho el retorno de la llamada recursiva.Muchos compiladores para optimizar cambiar una llamada recursiva a una cola recursivo o iterativo de la llamada.
Considere el problema de la computación factorial de un número.
Un enfoque sencillo sería:
factorial(n):
if n==0 then 1
else n*factorial(n-1)
Supongamos que la llamada factorial(4).La recursividad árbol sería:
factorial(4)
/ \
4 factorial(3)
/ \
3 factorial(2)
/ \
2 factorial(1)
/ \
1 factorial(0)
\
1
La máxima profundidad de la recursión en el caso anterior es O(n).
Sin embargo, considere el siguiente ejemplo:
factAux(m,n):
if n==0 then m;
else factAux(m*n,n-1);
factTail(n):
return factAux(1,n);
La recursividad árbol para factTail(4) sería:
factTail(4)
|
factAux(1,4)
|
factAux(4,3)
|
factAux(12,2)
|
factAux(24,1)
|
factAux(24,0)
|
24
Aquí también, la máxima profundidad de la recursión es O(n), pero ninguna de las llamadas agrega cualquier variable adicional a la pila.Por lo tanto, el compilador puede hacer con una pila.
Para entender algunas de las diferencias principales entre la cola de llamar la recursividad y no de la cola de llamadas recursividad podemos explorar la .NETO de las implementaciones de estas técnicas.
Aquí está un artículo con algunos ejemplos en C#, F# y C++\CLI: Aventuras en la Cola de la Recursividad en C#, F# y C++\CLI.
C# no optimizar la cola de llamar la recursividad mientras que F# no.
Las diferencias de principio de involucrar a los bucles vsCálculo Lambda.C# está diseñado con circuitos en mente, mientras que la F# es construido a partir de los principios de cálculo Lambda.Para una muy buena (y gratis) libro sobre los principios de cálculo Lambda, ver Estructura e Interpretación de los Programas de Ordenador, por Abelson, Sussman, y Sussman.
Con respecto a la cola de llamadas en F#, para un muy buen artículo introductorio, ver Introducción detallada a la Cola de Llamadas en F#.Finalmente, aquí está un artículo que cubre la diferencia entre el no-recursión de la cola y la cola-llamada de recursión (en F#): La cola de recursión vsno recursión de la cola en fa sostenido.
Si quieres leer sobre algunas de las diferencias de diseño de la cola de llamar la recursividad entre C# y F#, ver La generación de la Cola de llamadas código de operación en C# y F#.
Si te importa lo suficiente como para querer saber qué condiciones de evitar que el compilador de C# a partir de la realización de la cola de llamadas optimizaciones, consulte este artículo: JIT CLR cola-bases de la convocatoria.
Hay dos tipos básicos de recursiones: la cabeza de la recursividad y la cola de la recursividad.
En la cabeza de la recursividad, una función que hace que su llamada recursiva y, a continuación, realiza algunos cálculos más, tal vez usando el resultado de la llamada recursiva, por ejemplo.
En un la cola recursiva la función, todos los cálculos pasar primero y la llamada recursiva es la última cosa que sucede.
Tomado de este super impresionante post.Por favor, considere la posibilidad de la lectura.
Recursividad: una función se llama a sí mismo.Por ejemplo:
(define (un-ended name)
(un-ended 'me)
(print "How can I get here?"))
La cola de la Recursividad significa la recursividad a la conclusión de que la función:
(define (un-ended name)
(print "hello")
(un-ended 'me))
A ver, la última cosa de la onu-terminó la función (procedimiento, en el Esquema de la jerga) que hace es llamar a sí mismo.Otro (más útil) ejemplo:
(define (map lst op)
(define (helper done left)
(if (nil? left)
done
(helper (cons (op (car left))
done)
(cdr left))))
(reverse (helper '() lst)))
En el ayudante de procedimiento, la ÚLTIMA cosa que hace si la izquierda no es nil se llame a sí mismo (DESPUÉS de los contras de algo y cdr algo).Esto es básicamente como un mapa de una lista.
La cola de la recursividad tiene una gran ventaja que el intérprete (o compilador, depende del idioma y vendedor) puede optimizar, y transformarlo en algo equivalente a un bucle while.Como cuestión de hecho, en el Esquema de la tradición, la mayoría de "para" y ", mientras que" bucle se realiza en una cola de recursividad manera (no se para y mientras que, hasta donde yo sé).
Esta pregunta tiene una gran cantidad de respuestas...pero yo no puedo dejar timbre en una alternativa a tomar en cómo se define la "cola " recursividad", o al menos "correcto de la cola de la recursividad." A saber:se debe mirar como una propiedad de un particular expresión en un programa?O se debería ver como una propiedad de un la implementación de un lenguaje de programación?
Para más información sobre el último punto de vista, no es un clásico papel por Voluntad Clinger, "Correcto de la Cola de la Recursividad y el Espacio de la Eficiencia" (PLDI 1998), que define "correcto de la cola de la recursividad" como una propiedad de un lenguaje de programación de la aplicación.La definición está construido para permitir que uno de ignorar los detalles de implementación (por ejemplo, si la pila de llamadas es en realidad representada a través del tiempo de ejecución de la pila o a través de un montón asignado en la lista enlazada de cuadros).
Para lograr esto, se utiliza el análisis asintótico:no de la ejecución del programa tiempo como uno normalmente ve, pero en lugar de programa el uso del espacio.De esta manera, el uso del espacio de un montón asignado en la lista vinculada vs un tiempo de ejecución de la pila de llamada termina siendo asintóticamente equivalente;así se llega a ignorar que lenguaje de programación detalle de implementación (un detalle que sin duda importante en la práctica, pero puede enturbiar las aguas un poco cuando uno intenta determinar si una determinada aplicación es satisfacer el requisito de ser "propiedad recursiva de cola")
El papel es digno de un estudio cuidadoso para un número de razones:
Se da una definición inductiva de la la cola de expresiones y cola de llamadas de un programa.(Tal definición, y por qué este tipo de llamadas son importantes, parece ser el tema de la mayoría de las otras respuestas que se dan aquí.)
Aquí están las definiciones, sólo para proporcionar un sabor de los de texto:
Definición 1 El la cola de expresiones de un programa escrito en el Núcleo del sistema se define inductivamente como sigue.
- El cuerpo de una expresión lambda es una expresión de la cola
- Si
(if E0 E1 E2)es una cola de expresión, entonces ambosE1yE2son la cola de expresiones. - Nada más es una cola de expresión.
Definición 2 Un cola de llamadas es una cola de expresión que es una llamada a procedimiento.
(una cola de llamadas recursivas, o como dice el periódico, "auto-cola llamada" es un caso especial de una cola de llamadas, donde el procedimiento se invoca a sí misma).
Proporciona definiciones formales para seis diferentes "máquinas" para evaluar el Núcleo del Esquema, donde cada máquina tiene el mismo comportamiento observable de los excepto para el asintótica el espacio de la complejidad de la clase que cada uno está en.
Por ejemplo, después de dar definiciones para las máquinas con, respectivamente, de 1.basado en la pila de la memoria de gestión, 2.la recolección de basura, pero no de la cola de llamadas, 3.la recolección de basura y la cola de llamadas, el papel sigue adelante con las más avanzadas técnicas de almacenamiento de estrategias de gestión, tales como 4."evlis recursión de la cola", donde el medio ambiente no necesita ser preservada a través de la evaluación de la última sub-argumento de expresión en una cola de llamadas, 5.la reducción en el ambiente de cierre a sólo las variables libres de que el cierre, y 6.los llamados "seguros para el espacio de" la semántica definida por Appel y Shao.
Con el fin de demostrar que las máquinas que en realidad pertenecen a seis distintas espacio de la complejidad de las clases, de papel, para cada par de máquinas en comparación, proporciona ejemplos concretos de los programas que se exponen asintótica espacio de la voladura en una máquina, pero no en el otro.
(Leer más de mi respuesta ahora, no estoy seguro de si estoy logró capturar los puntos cruciales de la Clinger de papel.Pero, por desgracia, no puedo dedicar más tiempo al desarrollo de esta respuesta por el momento).
La función recursiva es una función que llama por sí mismo
Permite a los programadores escribir programas eficientes el uso de un la cantidad mínima de código.
La desventaja es que pueden causar bucles infinitos y otros resultados inesperados si no está escrito correctamente.
Voy a explicar tanto Función Recursiva Simple y la Cola de función Recursiva
Con el fin de escribir un Función recursiva Simple
- El primer punto a considerar es que cuando decides salir del bucle, que es el caso de bucle
- La segunda es ¿que hacer si somos nuestra propia función
Desde el ejemplo dado:
public static int fact(int n){
if(n <=1)
return 1;
else
return n * fact(n-1);
}
En el ejemplo de arriba
if(n <=1)
return 1;
Es el factor decisivo a la hora de salir del bucle
else
return n * fact(n-1);
Es el proceso
Permítanme el salto de la tarea uno por uno para una fácil comprensión.
Veamos lo que sucede internamente si me quedo fact(4)
- Sustituyendo n=4
public static int fact(4){
if(4 <=1)
return 1;
else
return 4 * fact(4-1);
}
If bucle de falla por lo que va a else bucle
así que devuelve 4 * fact(3)
En memoria de pila, tenemos
4 * fact(3)Sustituyendo n=3
public static int fact(3){
if(3 <=1)
return 1;
else
return 3 * fact(3-1);
}
If bucle de falla por lo que va a else bucle
así que devuelve 3 * fact(2)
Recordar que se llama ``4 * fact(3)`
La salida para fact(3) = 3 * fact(2)
Hasta ahora, la pila tiene 4 * fact(3) = 4 * 3 * fact(2)
En memoria de pila, tenemos
4 * 3 * fact(2)Sustituyendo n=2
public static int fact(2){
if(2 <=1)
return 1;
else
return 2 * fact(2-1);
}
If bucle de falla por lo que va a else bucle
así que devuelve 2 * fact(1)
Recuerdo que nos llama 4 * 3 * fact(2)
La salida para fact(2) = 2 * fact(1)
Hasta ahora, la pila tiene 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)
En memoria de pila, tenemos
4 * 3 * 2 * fact(1)Sustituyendo n=1
public static int fact(1){
if(1 <=1)
return 1;
else
return 1 * fact(1-1);
}
If loop es cierto
así que devuelve 1
Recuerdo que nos llama 4 * 3 * 2 * fact(1)
La salida para fact(1) = 1
Hasta ahora, la pila tiene 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1
Finalmente, el resultado de hecho(4) = 4 * 3 * 2 * 1 = 24
El La Recursividad De Cola sería
public static int fact(x, running_total=1) {
if (x==1) {
return running_total;
} else {
return fact(x-1, running_total*x);
}
}
- Sustituyendo n=4
public static int fact(4, running_total=1) {
if (x==1) {
return running_total;
} else {
return fact(4-1, running_total*4);
}
}
If bucle de falla por lo que va a else bucle
así que devuelve fact(3, 4)
En memoria de pila, tenemos
fact(3, 4)Sustituyendo n=3
public static int fact(3, running_total=4) {
if (x==1) {
return running_total;
} else {
return fact(3-1, 4*3);
}
}
If bucle de falla por lo que va a else bucle
así que devuelve fact(2, 12)
En memoria de pila, tenemos
fact(2, 12)Sustituyendo n=2
public static int fact(2, running_total=12) {
if (x==1) {
return running_total;
} else {
return fact(2-1, 12*2);
}
}
If bucle de falla por lo que va a else bucle
así que devuelve fact(1, 24)
En memoria de pila, tenemos
fact(1, 24)Sustituyendo n=1
public static int fact(1, running_total=24) {
if (x==1) {
return running_total;
} else {
return fact(1-1, 24*1);
}
}
If loop es cierto
así que devuelve running_total
La salida para running_total = 24
Finalmente, el resultado de hecho(4,1) = 24
Muchas personas ya han explicado recursividad aquí.Me gustaría citar un par de pensamientos acerca de algunas de las ventajas que la recursividad da del libro "la Simultaneidad en la .NET, los patrones Modernos de la programación paralela y concurrente" de Riccardo Terrell:
"Funcionales recursividad es la forma natural para recorrer en FP porque evita la mutación de estado.Durante cada iteración, un nuevo valor se pasa en el bucle de constructor, en lugar de ser actualizado (mutado).En además, una función recursiva puede ser compuesto, haciendo que su programa de más modular, así como la introducción de las oportunidades de explotar paralelización."
Aquí también se encuentran algunas notas interesantes desde el mismo libro sobre la cola de la recursividad:
La cola de llamar la recursividad es una técnica que convierte una regular recursiva función en una versión optimizada que puede manejar grandes entradas sin riesgos y efectos secundarios.
NOTA la principal razón por La cola de llamadas como la optimización es mejorar la situación de los datos, uso de memoria y el uso de la caché.Haciendo una cola llamada, el destinatario utiliza el mismo espacio de pila como el autor de la llamada.Esto reduce la presión de memoria.Es marginalmente mejora la memoria caché porque la misma la memoria es reutilizado para posteriores llamadas y puede permanecer en la caché, en lugar de desalojar a una antigua línea de caché para hacer espacio para un nuevo caché de la línea.
Un la cola recursiva la función es una función recursiva, donde la última operación que se hace antes de regresar es hacer la llamada a la función recursiva.Es decir, el valor de retorno de la llamada a la función recursiva es devuelto de inmediato.Por ejemplo, el código sería así:
def recursiveFunction(some_params):
# some code here
return recursiveFunction(some_args)
# no code after the return statement
Compiladores e intérpretes que implementar cola de llamadas de optimización o cola de llamadas eliminación puede optimizar el código recurrente para evitar desbordamientos de pila.Si el compilador o intérprete no aplicar la cola de llamadas de optimización (como el CPython intérprete) no hay ningún beneficio adicional a la escritura de su código de esta manera.
Por ejemplo, este es un estándar recursiva factorial función en Python:
def factorial(number):
if number == 1:
# BASE CASE
return 1
else:
# RECURSIVE CASE
# Note that `number *` happens *after* the recursive call.
# This means that this is *not* tail call recursion.
return number * factorial(number - 1)
Y esta es una cola llamada recursiva versión de la función factorial:
def factorial(number, accumulator=1):
if number == 0:
# BASE CASE
return accumulator
else:
# RECURSIVE CASE
# There's no code after the recursive call.
# This is tail call recursion:
return factorial(number - 1, number * accumulator)
print(factorial(5))
(Tenga en cuenta que aunque este es el código de Python, el CPython intérprete no hacer cola llamada optimización, por lo que la organización de su código como este no confiere ningún tiempo de ejecución de beneficio).
Puede que tenga que hacer su código un poco más ilegible para hacer uso de la cola de llamadas de optimización, como se muestra en el factorial ejemplo.(Por ejemplo, el caso base es ahora un poco intuitivo, y la accumulator parámetro es utilizado con eficacia como una especie de variable global.)
Pero el beneficio de la cola de llamadas de optimización es que evita el desbordamiento de la pila de errores.(Voy a tenga en cuenta que usted puede conseguir este mismo beneficio mediante el uso de un algoritmo iterativo en lugar de un recursiva uno.)
Desbordamientos de pila son causados cuando la pila de llamadas ha tenido demasiados marco de los objetos que se inserta en.Un marco de objeto se inserta en la pila de llamadas cuando se llama a una función, y se desprendió la pila de llamadas cuando se devuelve la función.Marco objetos contienen información como las variables locales y qué línea de código para volver a cuando se devuelve la función.
Si su función recursiva hace demasiadas llamadas recursivas sin regresar, la pila de llamadas puede exceder su marco de objeto límite.(El número varía según la plataforma;en Python es 1000 marco objetos de forma predeterminada). Esto provoca un desbordamiento de pila error.(Hey, que es donde el nombre de este sitio web proviene de!)
Sin embargo, si la última cosa que su función recursiva que hace es hacer la llamada recursiva y devolver su valor de retorno, entonces no hay ninguna razón por la que las necesidades para mantener el actual marco de objeto que se necesita para permanecer en la pila de llamadas.Después de todo, si no hay ningún código después de la llamada a la función recursiva, no hay ninguna razón para colgar en el marco actual del objeto de las variables locales.Así que puede deshacerse de la actual marco de objeto inmediato, en lugar de mantenerlo en la pila de llamadas.El resultado final de esto es que su pila de llamadas no crece en tamaño, y por lo tanto no puede desbordamiento de pila.
Un compilador o intérprete debe tener la cola de la llamada optimización de una función para que sea capaz de reconocer cuando la cola de la llamada optimización se puede aplicar.Incluso entonces, usted puede tener reorganizar el código en su función recursiva para hacer uso de la cola de llamadas de optimización, y es que si este potencial disminución en la legibilidad es digno de la optimización.
La cola de la Recursividad es bastante rápido en comparación a la normalidad de la recursión.Es rápido debido a la salida de los antepasados llamada no será escrito en la pila para mantener la pista.Pero en condiciones normales de recursividad todo el antepasado de las llamadas de salida por escrito en la pila para mantener la pista.
