Мне было интересно, если есть какой-то общий метод для преобразования "нормальной" рекурсии сfoo(...) + foo(...) как последний вызов хвостовой рекурсии.

Например (scala):

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

Общее решение для функциональных языков для преобразования рекурсивной функции в эквивалент хвостового вызова:

Простой способ - обернуть не хвостовую рекурсивную функцию вTrampoline монада.

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

Таким образом, функция Паскаля больше не является рекурсивной функцией. Тем не менее, Батутная монада является вложенной структурой вычислений, которые необходимо выполнить. В заключение,run является хвостовой рекурсивной функцией, которая проходит по древовидной структуре, интерпретирует ее и, наконец, в базовом случае возвращает значение.

Бумага от Рунара Бджанарсона на тему батутов:Stackless Scala со свободными монадами