Lo siguiente causaría desbordamiento de pila para 'n' grande, y puedo entender por qué.¿Por qué este código causa un desbordamiento de pila?
def factorial(n)
(n > 1) ? (return (n * factorial(n - 1))) : (return 1)
end
¿Por qué los siguientes causan desbordamiento también?
def factorial(n, k)
(n > 1) ? (return factorial(n - 1, lambda {|v| return k.call(v * n)})) : (return k.call(1))
end
Su segundo algoritmo crea un n -cadena larga de procedimientos lambda, cada uno con una referencia a la anterior. No sé exactamente qué hace Ruby, pero en un lenguaje correctamente recursivo la pila no se desbordó en tu segundo algoritmo, porque k.call en la lambda también está en posición de cola. Si, como sugiere el experimento de Brian, Ruby no tiene llamadas de cola adecuadas, la cadena larga de llamadas anidadas a la lambda desbordará la pila cuando se invoque el jefe de la cadena, aunque Ruby sea lo suficientemente inteligente como para convertir la cola -recursive factorial llamada en un bucle (= optimización de la cola de llamada).
La segunda versión todavía está recurriendo en factorial. Pensé que Ruby no hizo TCO. Pero no vuela la pila hasta que llega a las lambdas. Estoy confundido. (Todos los demás están aún más confundidos, o no leyeron la pregunta. Estoy bajando la votación de otros apropiadamente.) –
"Pero no explota la pila hasta que llega a las lambdas". - ¿Eh? No entiendo. –
Dado que el segundo ejemplo aún está volviendo a aparecer en 'factorial', esperaba que desbordara la pila antes de que llegara al caso base de' k.call (1) '. Pero en el segundo código de ejemplo anterior, las llamadas a 'factorial' no desbordan la pila (incluso para n muy grande), que es un comportamiento diferente al del primer ejemplo. El segundo ejemplo llega a ese caso base y no se desborda hasta que haya tenido lugar una gran cantidad de 'k.call'. Sin TCO, no veo cómo está llegando tan lejos. –
Como en la primera función, las llamadas recursivas pueden llegar a ser demasiadas para que el sistema las maneje.
En la mayoría de los idiomas, las llamadas a funciones van a la pila de llamadas , que en realidad es solo la pila. Llamar a una función recursivamente sigue agregando a la pila de llamadas. Eventualmente llenas la pila y obtienes un desbordamiento de pila. Eso siempre es un peligro cuando se ejecuta una función recursiva donde su nivel de recursión va a ser profundo.
-1: cf. "Lo siguiente se desbordará para 'n' grande, y puedo entender por qué" –
Por la misma razón, el primero tiene un desbordamiento de pila ... El espacio de llamadas se hace demasiado grande.
¿Desbordamiento? o StackOverflow ?! –
-1, pertenece a la uservoice. –