Optimización de Algoritmos con Tail Recursion

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.

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))

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)
     }