Me preguntaba si hay algún método general para convertir una recursión "normal" confoo(...) + foo(...) Como la última llamada a una recursión de cola.

Por ejemplo (scala):

def pascal(c: Int, r: Int): Int = {
 if (c == 0 || c == r) 1
 else pascal(c - 1, r - 1) + pascal(c, r - 1)
}

Una solución general para que los lenguajes funcionales conviertan la función recursiva a un equivalente de llamada de cola:

Una forma simple es envolver la función no recursiva de cola en elTrampoline monada.

def pascalM(c: Int, r: Int): Trampoline[Int] = {
 if (c == 0 || c == r) Trampoline.done(1)
 else for {
     a <- Trampoline.suspend(pascal(c - 1, r - 1))
     b <- Trampoline.suspend(pascal(c, r - 1))
   } yield a + b
}

val pascal = pascalM(10, 5).run

Así que la función pascal ya no es una función recursiva. Sin embargo, la mónada del trampolín es una estructura anidada del cálculo que se debe realizar. Finalmente,run es una función recursiva de la cola que recorre la estructura en forma de árbol, interpretándola y, finalmente, en el caso base devuelve el valor.

Un artículo de Rúnar Bjanarson sobre el tema de los Trampolines:Scala sin apilamiento con mónadas gratis