Мне было интересно, если есть какой-то общий метод для преобразования "нормальный" рекурсия с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