Recursividad en Scala

La recursividad es un método que divide el problema en subproblemas más pequeños y se llama a sí mismo para cada uno de los problemas. Es decir, simplemente significa que la función se llama a sí misma . Podemos usar recursión en lugar de bucles. La recursividad evita el estado mutable asociado con los bucles . La recursión es bastante común en la programación funcional y proporciona una forma natural de describir muchos algoritmos. La recursividad se considera importante en la programación funcional. Scala admite muy bien la recursión.

Entendamos usando el ejemplo factorial simple.
Ejemplo :

// Scala program of factorial using recursion
  
// Creating object
object GFG
{
    // Function define
    def fact(n:Int): Int=
    {
        if(n == 1) 1
        else n * fact(n - 1)
    }
      
    // Main method
    def main(args:Array[String])
    {
        println(fact(3))
    }
}

Producción:

6

El código anterior se demostró en un enfoque recursivo de una función factorial, donde la condición n == 1 da como resultado una ruptura de la recursividad.

Entendamos más claramente con un ejemplo de gcd.
Ejemplo :

// Scala program of GCD using recursion
  
// Creating object
object GFG
{
    // Function defined
    def gcd(x:Int, y:Int): Int=
    {
        if (y == 0) x
        else gcd(y, x % y)
    }
      
    // Main method
    def main(args:Array[String])
    {
        println(gcd(12, 18))
    }
}

Producción:

6

El problema con la recursión es que la recursión profunda puede explotar la pila si no tenemos cuidado.
Entendamos esto usando un ejemplo:
Código de ejemplo:

// Scala program of sum all numbers
// using recursion
   
// Creating object
object GFG
{
    // Function defined
    def sum(num: Int): Int=
    {
        if (num == 1)
            1
        else
            sum(num - 1) + num
    }
      
    // Main method
    def main(args:Array[String])
    {
        println(sum(55))
    }
}

Producción:

1540

El método sum hará la suma de todos los números. Reducimos el num cada vez y lo sumamos al resultado. Aquí, siempre que llamemos a sum, dejará el valor de entrada num en la pila y consumirá memoria cada vez. cuando intentamos pasar una entrada grande como sum(555555), la salida será java.lang.StackOverflowError . Esta salida significa que la pila se ha volado.

El ejemplo anterior no usa recursión de cola y, por lo tanto, no es un enfoque óptimo, especialmente si el valor inicial n es muy grande.

Las funciones recursivas de cola se consideran mejores que las funciones recursivas que no son de cola, ya que el compilador puede optimizar la recursividad de cola. Se dice que una función recursiva es cola recursiva si la llamada recursiva es lo último que hace la función. No hay necesidad de mantener un registro del estado anterior.
Entendámoslo con un ejemplo:

Ejemplo :

// Scala program of factorial using tail recursion
import scala.annotation.tailrec
  
// Creating object
object GFG
{
    // Function defined
    def factorial(n: Int): Int =
    {
        // Using tail recursion
        @tailrec def factorialAcc(acc: Int, n: Int): Int =
        {
            if (n <= 1)
                acc
            else 
                factorialAcc(n * acc, n - 1)
        }
        factorialAcc(1, n)
    }
      
    // Main method
    def main(args:Array[String])
    {
        println(factorial(5))
    }
}

Producción:

120

Aquí, en el código anterior, podemos usar la anotación @tailrec para confirmar que nuestro algoritmo es recursivo de cola.

Si usamos esta anotación y nuestro algoritmo no es recursivo de cola, el compilador se quejará. Por ejemplo, si intentamos usar esta anotación en el ejemplo anterior del método factorial, obtendremos el siguiente error en tiempo de compilación.

Ejemplo :

// Scala program of factorial with tail recursion
import scala.annotation.tailrec
  
// Creating object
object GFG
{
    // Function defined
    @tailrec def factorial(n: Int): Int =
    {
        if (n == 1)
            1
        else 
            n * factorial(n - 1)
    }
      
    // Main method
    def main(args:Array[String])
    {
        println(factorial(5))
    }
}

Producción:

Could not optimize @tailrec annotated method factorial: it contains a recursive call not in tail position