Welche dieser Funktionen sind tail rekursiv?

Question

let rec f1 = fun x -> if x = 0 then 1 else f1 (f1 0) in ... 

let rec f2 = fun x -> if x = 0 then foo x else f2 x in ... 

wo foo nicht Schwanz rekursiv

let rec f3 = fun x -> if x = 0 then foo x else f3 x in ... 

wo foo rekursive Schwanz

Answer 1

Alle von ihnen sind Schwanz rekursiv ist.

f1 enthält jedoch zwei rekursive Aufrufe, von denen nur der äußere ein Tail-Aufruf ist.

Für f2/f3, es spielt keine Rolle, ob foo ist Schwanz-rekursiv oder nicht, weil es nicht Teil der Rekursion von f2/f3 überhaupt.

Answer 2

Sie sollten nicht fragen, ob die Funktion tail rekursiv ist. Sie sollten fragen, ob alle Anrufe sind Tail-Anrufe. Ob foo tail rekursiv ist oder nicht, ist außerdem nicht relevant - ein Tail Call ist ein Tail Call unabhängig davon, welche Funktion er aufruft.

So nehmen wir sie einer nach dem anderen:

let rec f1 = fun x -> if x = 0 then 1 else f1 (f1 0) in ... 

Im else der inneren Ruf zu f1 ist kein Endrekursion. Der äußere ist. Beachten Sie, dass dies bedeutet, dass Sie abhängig davon, wie Sie den Begriff definieren, sagen können, dass diese Funktion Tail rekursiv ist (sie hat einen eigenen Tail Call) oder dass es nicht (es hat einen Non-Tail Call zu) selbst).

Deshalb ist es wichtig, sich auf zu konzentrieren, die Anrufe sind Tailaufrufe, nicht Tail-Rekursion! Eine Sprache mit Tail-Call Elimination wird dies für den äußeren Call tun, aber nicht für den inneren.

let rec f2 = fun x -> if x = 0 then foo x else f2 x in ... 
let rec f3 = fun x -> if x = 0 then foo x else f3 x in ... 

Die Anrufe foo und f2 sind Schwanz in beiden Fällen ruft. Auch hier ist es egal, was foo ist.