Zastanawiałem się, czy istnieje jakaś ogólna metoda konwersji „normalnej” rekursji za pomocąfoo(...) + foo(...) jako ostatnie wezwanie do rekursji ogonowej.

Na przykład (scala):

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

Ogólne rozwiązanie dla języków funkcjonalnych do konwersji funkcji rekurencyjnej na ekwiwalent połączenia ogonowego:

Prostym sposobem jest zawinięcie funkcji rekursywnej bez ogona wTrampoline monad.

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

Tak więc funkcja pascal nie jest już funkcją rekurencyjną. Jednakże monada trampoliny jest zagnieżdżoną strukturą obliczeń, którą należy wykonać. Wreszcie,run jest funkcją rekurencji ogonowej, która przechodzi przez strukturę podobną do drzewa, interpretując ją, aw końcu w przypadku bazowym zwraca wartość.

Artykuł Rúnara Bjanarsona na temat trampolin:Bezskala Scala z wolnymi monadami