Clase 14 de 36 • Curso de Scala básico
Contenido del curso
Briggi Rivera Guillén
Edward Basilio Cacho Casas
C. Daniel Sanchez R.
Carlos Yazid Padilla Royero
Jean Nuñez
Sabina Ixchel Garcia Mendoza
Juan Ochoa
Reinaldo Mendoza
Reinaldo Mendoza
Kevin Hernandez
Hola, ¿Podrías explicar más lo de la eficiencia?
Con respecto a la memoria: Yo entiendo que en cada llamada de la función se apila en memoria el contexto de la llamada es decir, variables locales, operandos temporales de expresiones (El caso del primer factorial), etc; pero en la segunda versión que hiciste en vez de usar un operando temporal usas un parámetro (que al final en el contexto de la función ocupa lo mismo que una variable local o un operando temporal).
Con respecto al tiempo de ejecución, no importa si la multiplicación se realiza en cada llamada o al final de todas, ya que las llamadas de funciones siempre tienen que retornar desde dónde fueron llamadas.
Tal vez Scala optimiza esto, y eso no lo sé, me podrías dar algún otro ejemplo de Tail Recursion por favor.
Sucede algo parecido a esto:
Recursión
(factorial 5) (* 5 (factorial 4)) (* 5 (* 4 (factorial 3))) (* 5 (* 4 (* 3 (factorial 2)))) (* 5 (* 4 (* 3 (* 2 (factorial 1))))) (* 5 (* 4 (* 3 (* 2 (* 1))))) (* 5 (* 4 (* 3 (* 2)))) (* 5 (* 4 (* 6))) (* 5 (* 24)) 120
Tail Recursion
(factorial 5) (fact-iter 1 1 5) #aquí tienes lo valores y solo multiplicas (fact-iter 1 2 5) # 1* 2 (fact-iter 2 3 5) # 2 * 3 (fact-iter 6 4 5) # 6 * 4 (fact-iter 24 5 5) # 24 * 5 (fact-iter 120 6 5) resultado = 120
@ecacho lo ha mostrado de una manera bastante gráfica :D
Como ejemplo extra, te puedo plantear el siguiente escenario:
En algunos tipos de sistemas como los videojuegos o en sistemas embebidos, es común el uso de un while infinito. Pero en lenguajes funcionales puros, no existe la instrucción while. Una manera de emular ese comportamiento es usando funciones recursivas que se llaman de forma infinita. Si no se tiene cuidado y la función recursiva no se hace con tail recursion en mente, eventualmente la memoria se va a llenar.
Aquí dejo el algoritmo Fibonnaci tanto Tail como no:
object fibonnaci_tail { def main(x: Int, y: Int = 1): Int = { x match case 0 | 1 => y case _ => main(x - 1, x) + main(x - 2, x - 2) } } /* main(5,1) => main(4,5) + main(3,3) => 8 main(4,5) => main(3,4) + main(2,2) => 5 main(3,4) => main(2,3) + main(1,1) => 3 main(2,3) => main(1,2) + main(0,0) => 2 + 0 main(1,1) => 1 main(2,2) => main(1,2) + main(0,0) => 2 + 0 => 2 main(3,3) => main(2,3) + main(1,1) => 3 main(2,3) => main(1,2) + main(0,0) => 2 + 0 => 2 main(1,1) => 1 */ fibonnaci_tail.main(5) object fibonnaci { def main(x: Int): Int = { x match case 0 | 1 => 1 case _ => main(x - 1) + main(x - 2) } } /* main(5) => main(4) + main(3) => 8 main(4) => main(3) + main(2) => 5 main(3) => main(2) + main(1) => 3 main(2) => main(1) + main(0) => 1 + 1 => 2 main(1) => 1 main(2) => main(1) + main(0) => 1 + 1 => 2 main(3) => main(2) + main(1) => 3 main(2) => main(1) + main(0) => 1 + 1 => 2 main(1) => 1 */ fibonnaci.main(5)
Tail recursion no sabia de esta forma de hacerlo, uffff esto puede ayudarme mucho en unas funciones que estoy implementado en un proyecto
Cómo funciona de manera interna la recursión computacional usando la función:
def factorial(n: Int): Int = { if (n == 0) 1 else n * factorial(n - 1) }
La función factorial es un ejemplo de una función recursiva, que se llama a sí misma repetidamente hasta alcanzar un caso base.
El funcionamiento interno de la recursión computacional puede entenderse siguiendo el flujo de ejecución de la función factorial.
Por ejemplo, si llamamos a factorial(3), la función primero evalúa la condición if (n == 0) y, como 3 no es igual a cero, se ejecuta el cuerpo del else. En este caso, n * factorial(n - 1) se convierte en 3 * factorial(2), y la función se llama a sí misma con un argumento de 2.
Luego, se repite el proceso para factorial(2), donde la expresión se convierte en 2 * factorial(1), y la función se llama a sí misma con un argumento de 1.
Para factorial(1), la expresión se convierte en 1 * factorial(0), y la función se llama a sí misma con un argumento de 0. En este punto, n == 0, por lo que se retorna 1.
A continuación, se retorna el valor 1 a la llamada de factorial(1), y la expresión completa se convierte en 1 * 1, lo que resulta en un valor de 1.
Luego, se retorna el valor 1 a la llamada de factorial(2), y la expresión completa se convierte en 2 * 1, lo que resulta en un valor de 2.
Finalmente, se retorna el valor 2 a la llamada de factorial(3), y la expresión completa se convierte en 3 * 2, lo que resulta en un valor de 6.
En resumen, la recursión computacional funciona mediante la ejecución repetitiva de una función que se llama a sí misma con argumentos diferentes hasta que se alcanza un caso base y se devuelve un resultado que se utiliza para calcular el valor de la expresión original.
Cómo funciona de manera interna la recursión computacional usando cuando n=3: def factorialTR(n: Int, acc: Int = 1): Int = { if (n == 0) acc else factorialTR(n - 1, acc * n) } Si n = 3, la función factorialTR se llamará inicialmente con los valores (3, 1) para los parámetros n y acc, respectivamente.
En la primera llamada, la condición if se evaluará como falsa (n no es igual a 0), por lo que se llamará a la función de nuevo con los valores (2, 3) para los parámetros n y acc, respectivamente.
En la segunda llamada, la condición if se evaluará nuevamente como falsa (n no es igual a 0), por lo que se llamará a la función de nuevo con los valores (1, 6) para los parámetros n y acc, respectivamente.
En la tercera llamada, la condición if se evaluará nuevamente como falsa (n no es igual a 0), por lo que se llamará a la función de nuevo con los valores (0, 6) para los parámetros n y acc, respectivamente.
En la cuarta llamada, la condición if se evaluará como verdadera (n es igual a 0), por lo que se retornará el valor de acc, que es 6.
Por lo tanto, el resultado de llamar a la función factorialTR con n = 3 es 6, ya que 3! (factorial de 3) es igual a 6.
Fuente chatGPT
Recursión
Una manera de abordar los problemas donde una función se llama a sí misma. Es la manera clásica de programar en lenguajes funcionales.
Es una pequieña modificación sobre un algoritmo recursivo con el objetivo de optimizar su ejecución.
Lo que se busca es no llenar el stack con llamadas, sino realizar la operación que queremos y pasar su acumulación al siguiente paso
def factorial(n: Long, resultado: Long = 1L): Long = if (n == 0) { println("Terminó") resultado } else { println(s"Va calculando ${n}, resultado: ${resultado}") factorial(n-1, n* resultado) } println(factorial(3))
memoization
creo que scalafiddle ya no existe mas
def factorial(n: Long, resultado: Long = 1L): Long = if(n==0){ println("Termino") resultado } else { println(s"Va calculando ${n}, resultado: ${resultado}") factorial(n-1, n*resultado) }
