9

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?

1
  • 2
    El artículo sobre recursión de la Wikipedia tiene una sección específica para la recursión de cola que explica en qué consiste y las ventajas de usarla.
    – Alvaro Montoro
    Commented el 4 dic. 2017 a las 20:49

2 respuestas 2

14
+50

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.

3
  • 1
    Puedes añadir que existe una anotacion llamada tailrec . Un método anotado con tailrec estará optimizado por el compilador o saltará un warning. Es una buena forma de asegurarte de que un método es realmente tail recursive. Commented el 4 dic. 2017 a las 10:55
  • 1
    Gracias @Daniel. Agregado.
    – sstan
    Commented el 4 dic. 2017 a las 13:23
  • Excelente Respuesta! Muchas gracias quedo muy claro @sstan Commented el 6 dic. 2017 a las 2:28
6

Ya está bien respondida por @sstan, así que no voy a profundizar mucho en lo que es la optimización de recursividad de final de cola. Tan sólo comentar que ni es mejor ni es peor que lo que llamas recursividad normal. Tiene sus ventajas para algunos casos, pero es mejor que el compilador elija la mejor manera de implementar la recursividad.

Al llamar a una función se crea un nuevo entorno donde ejecutar el código de la función. Este entorno se conoce por clausura (closure) y es primordial en todo lenguaje funcional. Desde el punto de vista de la programación orientada a objetos, también puede verse la clausura como una instancia de la función y a ésta como si fuera una clase.

Cada vez que se invoca a una función, se crea una clausura, que permanecerá activa hasta que la función acabe. Gracias a esta clausura, la función puede llamar a otras funciones y continuar en el punto donde estaba con tan sólo sustituir la función invocada por el valor retornado (A ésto se lo conoce por "Transparencia Referencial"). Así mismo, gracias a que una clausura mantiene su estado de ejecución, es posible interceptar los errores producidos en la función que hemos llamado y así tratar de corregirlos.

En el caso de funciones que se llaman a sí mismas (aka "llamada recursiva"), en cada llamada se crean clausuras casi idénticas a la anterior. Si estamos seguros que esta llamada está al final de la cola de llamadas, o lo que es lo mismo, si podemos sustituir la pila de llamadas por el valor retornado sin necesidad de hacer más operaciones, sería posible usar una única clausura para todas las llamadas de la función. De este modo nos ahorraríamos recursos al no tener que generar todas las clausuras, aunque a cambio perderíamos la posibilidad de interceptar errores y la ventaja de tener "evaluaciones perezosas".

Lo de "evaluación perezosa" vale la pena comentarlo. Se dice que una evaluación es perezosa si únicamente se computan los valores que son estrictamente necesarios para obtener el resultado. Una de las características de la programación funcional es precisamente poder diferir lo más posible el cálculo hasta el final de la secuencia de operaciones y así descartar operaciones que no van a influir en el resultado final.

El estado actual de los compiladores (en programación funcional) permite ya inferir qué operaciones no son necesarias realizar o qué tipo de optimizaciones mejoría la ejecución (tailrec opt, inline call, etc). En general, el compilador creará la mejor versión siguiendo la ayuda que podamos darle.

Por poner un ejemplo, podemos dar la siguiente definición de la función de Fibonacci:

def fib(n: Int): BigInt = n match {
  case 0 => 1
  case 1 => 1
  case _ => fib(n-1) + fib(n-2)
}

Esta definición no sería tailrec. Podemos crear una versión que lo sea:

@tailrec 
def fib(n: Int, v: BigInt=0, acc: BigInt=1): BigInt =
  if (n == 0)
    acc
  else
    fib(n-1, acc, acc+v)

Esta versión tailrec no tendrá problemas con la memoria y será, seguramente, mucho más rápida que la versión anterior. Aún así, no es la mejor versión. Por dar ideas, se podrían guardar los resultados intermedios para no tener que calcularlos siempre, a costa de gastar un poco más de memoria (aka "memoization").

Pero veamos esta otra versión perezosa:

val fib: Stream[BigInt] =
  BigInt(1) #:: BigInt(1) #:: (fib zip fib.tail) map {case (a,b) => a+b}

Estamos definiendo fib en función de sí misma, lo que da una secuencia infinita. La particularidad de usar Streams es que su expansión se realiza a medida que vayamos descubriendo nuevos elementos (evaluación perezosa), almacenándose los elementos a medida que se calculan. Es un modo sencillo de calcular la secuencia de fibonacci y más eficiente que con la versión tailrec anterior.

Espero haberte aclarado algo.

2
  • Gracias por profundizar y agregar este aporte! @ChemaCortes , para aclarar y ver si entendí xD, se pudiera decir que con tail recursion estaríamos perdiendo la ventaja de la evaluación perezosa? Commented el 6 dic. 2017 a las 2:43
  • 1
    Así es, aunque no diría que sea mejor o peor. Tan sólo tener en cuenta que en programación funcional existen otros modos de hacer las cosas. Commented el 6 dic. 2017 a las 12:15

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.