Wie würde ich diesen Schwanz rekursiv machen?

Die Tail-Rekursion ist einfach für Dinge zu schreiben, die iterativ sind. Ihre Funktion ruft sich oft selbst auf, daher wird es nicht einfach sein. Dennoch kann jedes Programm iterativ gemacht werden (z. B. ist Ihr Computer eine riesige iterative Maschine), so dass es gemacht werden kann.

Zunächst ist Ihre Funktion nicht direkt rekursiv (d. h. prog1 ruft sich nicht direkt auf). Stattdessen ruft prog1 map auf, das dann das Lambda aufruft, das Sie ihm gegeben haben (vielleicht mehrere Male), das dann prog1 aufruft; also ist es indirekt. Der Aufruf von map ist kein Tail Call; Der Aufruf von map an das Lambda ist sicherlich kein Tail Call (es muss vielleicht mehr als einmal aufgerufen werden); und der Aufruf von Lambda an prog1 ist ein Tail Call.

Daher bin ich mir nicht sicher, was genau Sie benötigen, wenn Sie darum bitten, "tail rekursiv" zu sein. Möchten Sie, dass jeder Anruf in der Anrufkette von prog1 für sich selbst ein Tail-Call ist? Oder möchtest du jeden Aufruf im Programm einen Tail Call machen? Es gibt "tail-rekursive" Versionen von map , aber sie sind nur "tail rekursive" in Bezug auf Aufrufe von map nach map und nicht Aufrufe der Mapping-Funktion, so dass sie für Ihren Fall nicht nützlich sind .

Die allgemeine Methode, jeden Aufruf in einem Programm zu einem Tail-Call zu machen, heißt Fortsetzungsstil . Grundsätzlich übernimmt jede Funktion ein zusätzliches Funktionsargument, die "Fortsetzung". Anstatt einen Nicht-Tail-Aufruf an eine Funktion zu senden, machen Sie stattdessen einen Tail-Aufruf an eine Funktion und übergeben ihr eine Weiterleitung, die angibt, wie die Ergebnisse des Funktionsaufrufs verarbeitet werden sollen. Im Grunde würde die Fortsetzung den "Rest" der ursprünglichen Funktion nach dem Nicht-Tail-Aufruf umfassen und das "Rückgabeergebnis" des ursprünglichen Nicht-Tail-Aufrufs als ein Argument annehmen. Ich werde es als eine Übung verlassen, wie Sie Ihr Programm in CPS konvertieren.