Tail recursion

Cuando me tocaba enseñar recursibidad, hago el típico ejemplo de la Sucesión de Fibonacci la cual podríamos definir de este modo :

f(0) = 1
f(1)= 1
f(n) = f(n - 1) + f(n - 2)

Y listo! esto es muy fácil de programar en scala, sería:

def fibo(n: Int) : Long = if (n==0 || n==1) 1 else fibo(n-1) + fibo(n-2)

esto funciona si no pretendemos calcular el fibonacci en la posición  n = 55

El problema es que este algoritmo tiene una complejidad de dos a la n.

Podemos resolver este problema empezando desde el comienzo. Si lo pensamos de forma imperativo, sería algo así :

  def fibonacci(n: Int): Long = {
     var fa = 1l
     var faa = 1l
     var i = 1
    while (i < n) {
      var aux = fa
      fa = fa + faa
      faa = aux
      i = i + 1
    }
    faa
  }

Es decir si empezamos desde el principio ya tenemos los f(n-1) y f(n-2), pero no solo es solucionable de este modo de forma imperativa, tambien podemos utilizar recursividad de este modo :

  def fibonacci(n: Int): Long = {
     def fibonacciAux(n: Int, fa: Long, faa: Long) : Long =
       if (n == 3) fa + faa
       else fibonacciAux(n-1, fa + faa, fa)

    if (n<=2) 1
    else fibonacciAux(n,1,1)
  }


Tail recursion 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.

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.

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.

Y listo! La función de fibonacci funciona rápido porque utilizamos tail recursion y porque bajamo su complejidad.

Dejo link :
https://es.stackoverflow.com/questions/121965/que-es-tail-recursion