#Kata Tail recursion en Scala.

En este post te voy a explicar como funciona Tail Recursion (@tailrec) en Scala.

¿Qué es tail recursion?

La recursividad es la capacidad de una función o método de llamarse a sí misma. Cada vez que se hace una llamada al mismo método se agrega a la pila de funciones, lo que incrementa el uso de memoria. La recursividad no es gratuita, tiene un coste.

La recursividad de cola, consiste en no agregar una llamada adicional a la pila de funciones cuando se ejecuta una función recursiva, y ejecutar el mismo método en el contexto.

Desventajas

En el caso de Scala, si no planteas bien el caso base y haces uso de @tailrec, puedes generar un bucle infinito de llamadas que no arrojara una Stack Overflow exception.

No todos los problemas que resuelves con recursividad normal podrán ser implementados con @tailrec, incluso es posible que necesites modificar el código para que pueda compilar.

Recursion versus tail recursion.

He escrito un ejemplo, una función factorial, junto con Fibonacci, uno de los ejemplos más comunes para explicar
recursividad. En el caso base, que es uno, agregue una excepción para poder visualizar  el stack trace. Te muestro:

Las stacktraces.

Te muestro la salida del programa, primero con recursion normal, luego con tailrec.

 

 

Gustavo Sánchez
Últimas entradas de Gustavo Sánchez (ver todo)

Soy especialista en escribir software de calidad. Mediante el uso de marcos de trabajo, técnicas y automatización de procesos he podido reducir los costes operativos de los sistemas de la empresa. Sistemas confiables y adaptables producen clientes felices.