No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Tail recursion

14/36
Recursos

Aportes 6

Preguntas 0

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸n.

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

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

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