Funciones recursivas en scala

Las funciones son una parte clave de los lenguajes de programación modernos. en OOP se les llaman métodos; en el mundo funcional su nombre son “funciones” y son tratados como objectos.

comencemos con una definición. una función recursiva es una función que se llama a si misma. Es importante que este tipo de funciones tengan una condición de parada. o si no, estaríamos creando un loop infinito.

la recursion se puede aplicar en muchos problemas. los cuales, en muchos casos, se resuelven con un loop o un while. por ejemplo, como calcular la suma de todos los números entre dos números? por ejemplo, podríamos crear un arreglo de todos los elementos, entre esos dos números, y luego sumarlos todos.

esto mismo, se puede hacer de manera recursiva:

como veras, la suma recursiva retorna la expresión a+sumaRecursiva(a+1,b) hasta que todos los elementos se agreguen a la lista.

Este segundo método recursivo es mas conciso, pero tiene un problema – StackOverflowError. ya que la recursion es interpretado por la JVM como una llamada regular a un método, implica el uso de un frame adicional en la pila de llamadas por llamada recursiva. entonces, si el numero de llamadas recursivas excede el limite de la pila, obtenemos el error de StackOverflow.

“Tail Recursion”

si quieres estar seguro que las llamadas recursivas no provoquen un StackOverflowError, necesitas transformar esa llamada recursiva a una “tail recursion”. Pero que es “tail recursion”? tail recursion es una función donde la ultima acción de la invocación es una llamada recursiva. por ejemplo:

en el código de arriba, declaramos una función dentro de otra función. la anotcacion @tailrec indica que la función es del tipo “tail recurcion“. no es obligatorio poner esa anotación, pero valida y optimiza la función para este tipo de llamadas.

gracias a este tipo de optimización de scala, ya no tenemos que preocuparnos del error de StackOverflow, por que la JVM lo interpretara como un loop normal.

otro ejemplo, podría ser calcular el máximo común divisor.