Ich habe mich gefragt, ob es eine allgemeine Methode gibt, um eine "normale" Rekursion mit zu konvertierenfoo(...) + foo(...) als letzter aufruf zu einer schwanzrekursion.

Zum Beispiel (scala):

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

Eine allgemeine Lösung für funktionale Sprachen zum Konvertieren rekursiver Funktionen in ein Tail-Call-Äquivalent:

Eine einfache Möglichkeit besteht darin, die nicht schwanzrekursive Funktion in die Zeichenfolge "."Trampoline Monade.

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

Die Pascal-Funktion ist also keine rekursive Funktion mehr. Die Trampolin-Monade ist jedoch eine verschachtelte Struktur der Berechnung, die durchgeführt werden muss. Endlich,run ist eine rekursive Schwanzfunktion, die durch die baumartige Struktur geht, sie interpretiert und schließlich im Basisfall den Wert zurückgibt.

Ein Beitrag von Rúnar Bjanarson zum Thema Trampoline:Stackless Scala Mit Freien Monaden