Introducción a Scala y configuración del entorno de desarrollo

1

Introducción al curso y presentación de los objetivos

2

Programación Funcional en Scala: Fundamentos y Beneficios

3

Instalación y configuración de herramientas para programar en Scala

4

Herramientas Esenciales para Programar en Scala

5

Hola Mundo en Scala con ScalaFiddle

Fundamentos de Programación Funcional

6

Tipos de Datos Básicos en Scala

7

Inmutabilidad en Programación Funcional con Scala

8

Expresiones en Scala: Conceptos y Ejemplos Prácticos

9

Funciones en Programación Funcional y Matemática

10

Colecciones Inmutables en Lenguajes Funcionales

11

Tuplas y objetos en programación funcional y orientada a objetos

12

Uso de `copy()` y Lentes en Programación Funcional

Conceptos básicos de Programación Funcional

13

Programación Funcional: Uso de Pattern Matching Avanzado

14

Optimización de Algoritmos con Tail Recursion

15

Agregación y acumuladores en programación funcional con Scala

Fundamentos teoricos

16

Funciones Totales y Parciales en Programación Funcional

17

Razonamiento Inductivo en Algoritmos Recursivos

18

Razonamiento con Tipos en Lenguajes Tipados y Dinámicos

19

Uso de Traits en Scala: Concepto y Ejemplos Prácticos

20

Tipos Genéricos en Programación: Uso y Ejemplos Prácticos

21

Tipos de Datos Algebraicos: Suma y Producto en Programación

22

Evaluación Perezosa en Scala: Variables y Colecciones Lazy

23

Manejo de Disyunciones Option en Programación Funcional

24

Manejo de Excepciones con Try y Either en Programación Funcional

Proyecto de Backend

25

Desarrollo de Backend con PlayFramework y Scala: Proyecto Platzi Video

26

Modelo de Actores en Scala: Akka y Erlang

27

Modelo de Datos y Configuración de Proyecto con Play Framework

28

Integración de Play con Slick y SQLite en Scala

29

Consultas Asíncronas y Futuros en Scala con Slick

30

Creación, actualización y eliminación de datos en bases de datos

31

Computación Paralela y Asíncrona en Scala: Conceptos y Aplicaciones

32

Serialización de Datos en Scala con Play Framework

33

Serialización y validación de JSON a objetos Scala

34

Manejo de Errores en Scala: Técnicas y Pruebas con Postman

35

Exportación de Aplicaciones Play con SBT Native Packager

Conclusiones

36

Conceptos Clave de la Programación Funcional en Scala

No tienes acceso a esta clase

¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera

Curso de Scala básico

Curso de Scala básico

Carlos Daniel Sanchez

Carlos Daniel Sanchez

Optimización de Algoritmos con Tail Recursion

14/36
Recursos

¿Qué es la recursión y por qué puede ser ineficiente?

La recursión se refiere a una técnica algorítmica en la que una función se llama a sí misma, y es comúmmente utilizada en programación funcional y algoritmos complejos como los de machine learning. Aunque es una herramienta poderosa, la recursión puede ser ineficiente en términos computacionales. Esto se debe a que cada llamada recursiva debe esperar a la resolución completando todas las llamadas antes de comenzar a multiplicar o resolver la última tarea, lo cual puede consumir mucha memoria.

¿Cómo funciona el cálculo del factorial con recursión?

El factorial de un número, indicado como n!, se calcula multiplicando todos los números enteros desde 1 hasta n. Por ejemplo, 3! se calcula como 1 * 2 * 3. Utilizando una función recursiva básica, podemos implementarlo así:

Ejemplo en código: recursión básica

fun factorial(n: Long): Long {
    return if (n == 0L) 1
    else n * factorial(n - 1)
}

Este enfoque sigue el clásico procedimiento recursivo, pero no inicia los cálculos hasta resolver todas las subllamadas, lo cual acumula datos en la memoria de la llamada.

¿Qué es la recursión de cola (Tail Recursion)?

La recursión de cola es una técnica de optimización que resuelve los problemas de eficiencia de la recursión clásica. En esta técnica, la operación de cada paso recursivo se realiza antes de la llamada recursiva, permitiendo que el cálculo se lleve a cabo sin tener que reservar espacio adicional en el stack para las operaciones pendientes.

Ejemplo en código: tail recursion

tailrec fun factorial(n: Long, resultado: Long = 1): Long {
    return if (n == 0L) resultado
    else factorial(n - 1, n * resultado)
}

En este caso, cada paso recursivo envía el producto acumulado a la siguiente llamada recursiva. Esta pequeña modificación optimiza el algoritmo considerablemente, reduciendo la carga en memoria y aumentando la eficiencia.

¿Cuáles son las ventajas y limitaciones de la recursión de cola?

Ventajas

  • Eficiencia en tiempo y espacio: Al realizar las operaciones antes de la llamada recursiva, la recursión de cola disminuye el uso de memoria y mejora el tiempo de ejecución.
  • Optimización automática: Muchas máquinas virtuales y compiladores modernos optimizan automáticamente las funciones tail recursive, eliminando llamadas redundantes.

Limitaciones

  • Complejidad estructural: Requiere estructurar cuidadosamente el código recursivo, lo que puede ser menos intuitivo para los principiantes.
  • Uso específico: No todos los problemas algorítmicos se pueden resolver fácilmente con tail recursion. Debe ser usado en contextos apropiados donde se puede aplicar la conversión.

¿Cómo optimizar nuestros algoritmos recursivos?

Si buscas optimizar algoritmos recursivos, aquí tienes algunos consejos prácticos:

  1. Identifica Tail Recursion: Asegúrate de que tu función recursiva realice operaciones antes de efectuar la llamada recursiva.
  2. Usa lenguaje o compiladores que soporten esta optimización: Algunos lenguajes y entornos optimizan automáticamente la recursión de cola.
  3. Considera otros paradigmas: A veces, un enfoque iterativo o una técnica alternativa podría ser más eficiente y sencilla de implementar.

La recursión de cola no es una herramienta de uso diario en programación, pero comprenderla te prepara para escribir algoritmos más eficientes. Con la práctica, puedes aprender a escoger el mejor enfoque para cada problema que enfrentes. ¡Sigue explorando y mejorando tus habilidades en programación algorítmica!

Aportes 7

Preguntas 0

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad?

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

Aquí dejo el algoritmo Fibonnaci tanto Tail como no: ```js 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) ```

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