¿Que es tail-recursion?

publicado por: Anonymous

Aprendiendo Scala como lenguaje de programación me encontré con el termino tail-recursión , lo que supone ser mejor que una recursión normal ¿Que significa esto?

solución

Tail recursion (o recursividad de cola?) es un tipo específico de recursión. En particular, se dice que una función recursiva usa tail recursion si la llamada a sí misma ocurre como la última acción de la función.

Para entender un poco mejor, digamos que queremos escribir una función recursiva def sum(n: Int): Long, que si le pasamos el parámetro n = 5, entonces el resultado es la suma siguiente: 5 + 4 + 3 + 2 + 1 = 15.

Comparemos 2 formas diferentes de implementar este algoritmo, en el primer caso usando una función recursiva normal, y en el segundo usando tail recursion.

1. Función recursiva normal

def sum(n: Int): Long =
    if (n <= 0)
        0
    else
        n + sum(n - 1)

En este caso, la función no usa tail recursion porque aunque la llamada recursiva sum(n - 1) aparece al final de la función, en realidad no es la última acción. En realidad, para completar esa sentencia, primero tiene que ejecutar sum(n - 1) y luego se requiere la etapa adicional de sumar el resultado a n.

2. Función recursiva con tail recursion

def sum(n: Int, total: Long = 0): Long =
    if (n <= 0)
        total
    else
        sum(n - 1, total + n)

Aunque esta función produce resultados idénticos a la función anterior, esta sí se puede decir que usa tail recursion porque la llamada recursiva sum(n - 1, total + n) sí es la última acción de la función.

¿Qué importancia tiene el que la función recursiva use “tail recursion” o no?

Cuando una función recursiva se llama a sí misma varias veces, las llamadas van acumulándose en la pila de llamadas, que de por sí, no es muy eficiente porque consume memoria. Pero aun peor, si se acumulan demasiadas llamadas en esta pila, eventualmente se desborda la pila de llamadas y te lanza la excepción java.lang.StackOverflowError.

Esto lo podemos observar si ejecutamos la función recursiva normal con un valor n muy elevado:

println(sum(1000000))

Demo de función recursiva normal

Resultado:

java.lang.StackOverflowError
  at Rextester$.sum(source.scala:12)
  at Rextester$.sum(source.scala:12)
  at Rextester$.sum(source.scala:12)
  ...

Esta ineficiencia es un problema serio para un lenguaje funcional como Scala que promueve el uso de funciones recursivas.

Sin embargo, cuando Scala detecta que la función recursiva usa tail recursion, entonces el compilador es capaz de efectuar una optimización al código de forma automática, efectivamente eliminando la recursividad enteramente y reemplazándolo con un simple bucle. Esta optimización es comúnmente conocida como tail call optimization.

Usando la sintaxis Java por un momento, es como si el compilador transformara la función recursiva con tail recursion al código siguiente sin recursividad (más o menos):

long sum(int n) {
    long total = 0;
    while(true) {
        if (n <= 0) {
            return total;
        } else {
            total += n;
            n -= 1;
        }
    }
}

Debido a esta transformación automática, el uso de memoria se mantiene constante sin importar el valor asignado a n, y se evita por completo el riesgo de desbordar la pila de llamadas (StackOverflowError):

println(sum(1000000))

Demo de función recursiva con tail recursion

Resultado:

500000500000

Conclusión

Debido a la optimización automática que Scala aplica a las funciones recursivas con tail recursion, vale la pena tratar de ajustar el algoritmo de una función recursiva, cuando es posible hacerlo, para que use tail recursion. En particular, es importante hacerlo si la función efectua varias llamadas recursivas, para evitar consumir demasiada memoria, o hasta desbordar la pila de llamadas.

Es de notar que muchos otros lenguajes de programación, incluyendo Java, no incluyen esta optimización automática. Pero siendo que Scala es un lenguaje funcional que promueve el uso liberal de las funciones recursivas, tiene sentido que su compilador incluya esta optimización para minimizar su impacto en rendimiento y memoria.

Adicionalmente, aun si utilizamos otro lenguaje de programación que no incluye esta optimización automática, es bueno estar al tanto de lo que es tail recursion. Porque habrá veces donde será necesario optimizar una función recursiva de forma manual para corregir problemas de memoria o desbordamiento de pila de llamadas. En esos casos, la clave es buscar la forma de rediseñar la lógica de la función para que use tail recursion. Si esto se puede lograr, luego es trivial convertir manualmente la lógica para usar un bucle en vez de recursividad.

Edición – usando la anotación @tailrec para garantizar el uso de “tail recursion”

Scala permite anotar funciones recursivas con la anotación @tailrec (scala.annotation.tailrec). Al agregar esta anotación, el compilador verifica que la función recursiva de verdad está usando tail recursion y te marca un error si no es el caso. Es una buena manera de confirmar que la función va a beneficiarse de la optimización automática y de que no nos hemos equivocado en el diseño de la función.

Para observar como funciona esto, tomemos nuevamente las 2 funciones recursivas anteriores y agreguemos la anotación a ambas. Primero, la función recursiva normal:

@tailrec def sum(n: Int): Long =
    if (n <= 0)
        0
    else
        n + sum(n - 1)

Demo de función recursiva normal anotada con @tailrec

Resultado:

Error(s), warning(s):
source_file.scala:13: error: could not optimize @tailrec annotated method sum: it contains a recursive call not in tail position
            n + sum(n - 1)
              ^
one error found

Como vemos, el compilador nos está advirtiendo que la función no usa tail recursion.

Pero si ahora le aplicamos la anotación a la función recursiva que sí usa tail recursion:

@tailrec def sum(n: Int, total: Long = 0): Long =
    if (n <= 0)
        total
    else
        sum(n - 1, total + n)

Demo de función recursiva con tail recursion anotada con @tailrec

Resultado:

500000500000

En este caso, el compilador no marca error, confirmando que la función en efecto usa tail recursion y que va a beneficiarse de la optimización automática del compilador.

Respondido por: Anonymous

Leave a Reply

Your email address will not be published. Required fields are marked *