En una prueba parcial para la preparación de GATE había una pregunta:
f(n):
if n is even: f(n) = n/2
else f(n) = f(f(n-1))
Respondí "Terminará para todos los enteros", porque incluso para algunos enteros negativos, terminará como Error de desbordamiento de pila .
Pero mi amigo no estuvo de acuerdo en decir que, dado que este no es un código implementado y solo un pseudocódigo, será una recursión infinita en el caso de algunos enteros negativos.
¿Qué respuesta es correcta y por qué?
algorithms
recursion
pseudocode
Prakhar Londres
fuente
fuente
while (true);no terminará ni, en nada sensato, provocará el desbordamiento de la pila.while(true);de una manera que use cualquier pila definitivamente no sería sensata . El punto es que, a menos que deliberadamente haya hecho todo lo posible para ser incómodo,while(true);no terminará ni activará el desbordamiento de la pila.Respuestas:
La respuesta correcta es que esta función no termina para todos los enteros (específicamente, no termina en -1). Su amigo tiene razón al afirmar que se trata de pseudocódigo y que el pseudocódigo no termina en un desbordamiento de pila. El pseudocódigo no está formalmente definido, pero la idea es que haga lo que dice la lata. Si el código no dice "terminar con un error de desbordamiento de pila", entonces no hay error de desbordamiento de pila.
Incluso si este fuera un lenguaje de programación real, la respuesta correcta sería "no termina", a menos que el uso de una pila sea parte de la definición del lenguaje. La mayoría de los lenguajes no especifican el comportamiento de los programas que pueden desbordar la pila, porque es difícil saber con precisión cuánta pila usará un programa.
Si ejecutar el código en un intérprete o compilador real provoca un desbordamiento de la pila, en muchos idiomas, es una discrepancia entre la semántica formal del lenguaje y la implementación. En general, se entiende que las implementaciones de un lenguaje solo harán lo que se puede hacer en una computadora concreta con memoria finita. Si el programa muere con un desbordamiento de pila, se supone que debe comprar una computadora más grande, recompilar el sistema si es necesario para admitir toda esa memoria e intentarlo nuevamente. Si el programa no finaliza, es posible que deba seguir haciendo esto para siempre.
Incluso el hecho de que un programa desborde o no la pila no está bien definido, ya que algunas optimizaciones, como la optimización y la memorización de llamadas de cola, pueden permitir una cadena infinita de llamadas a funciones en un espacio de pila con límite constante. Algunas especificaciones de lenguaje incluso exigen que las implementaciones realicen la optimización de llamadas de cola cuando sea posible (esto es común en lenguajes de programación funcionales). Para esta función, se expande a ; la llamada externa a es una llamada de cola, por lo que no empuja nada en la pila, por lo tanto solo va a la pila, y eso regresa , por lo que la pila vuelve al mismo estado en el que estaba al principio. Por lo tanto, con la optimización de llamadas de cola se repite para siempre en la memoria constante.
f(-1)f(f(-2))ff(-2)-1f(-1)fuente
let f :: Int -> Int; f n = if even n then n `div` 2 else f (f (n - 1)) in f (-1)Si miramos esto en términos del lenguaje C, una implementación es libre de reemplazar código con código que produce el mismo resultado en todos los casos en que el original no invoca un comportamiento indefinido. Entonces puede reemplazar
con
Ahora la implementación puede aplicar la recursividad de cola:
Y esto se repite para siempre si y solo si n = -1.
fuente
f(-1)es un comportamiento indefinido (la implementación puede suponer que cada hilo termina o hace algo más en una breve lista de actividades que esta función no realiza), por lo que el compilador puede hacer lo que quiera ¡caso!