Tail-Rekursion vs. Vorwärts-Rekursion

Question

Kann mir jemand den Unterschied zwischen diesen beiden Arten Rekursionen und Beispiel (speziell in OCaml) geben?

Answer 1

Eine rekursive Schwanzfunktion ist eine Funktion, bei der der einzige rekursive Aufruf der letzte in der Funktion ist. Eine rekursive Nicht-Tail-Funktion ist eine Funktion, bei der dies nicht der Fall ist.

Eine Rückwärtsrekursion ist eine Rekursion, bei der in jedem rekursiven Aufruf der Wert des Parameters kleiner ist als im vorherigen Schritt. Eine Vorwärtsrekursion ist eine Rekursion, bei der sie mit jedem Schritt größer wird.

Dies sind zwei orthogonale Konzepte, d. H. Eine Vorwärtsrekursion kann tail-rekursiv sein oder nicht und dasselbe gilt für Rückwärtsrekursionen.

Zum Beispiel die Fakultätsfunktion oft wie dies in imperativen Sprachen geschrieben:

fac = 1 
for i from 1 to n: 
    fac := fac * i 

Die gemeinsame rekursive Version von Fakultäts zählt rückwärts (dh es nennt sich mit n-1 als Parameter), können Sie jedoch, wenn würde Wenn Sie die obige imperative Lösung direkt übersetzen, erhalten Sie eine rekursive Version, die aufwärts zählt. Es würde wie folgt aussehen:

let fac n = 
    let rec loop i = 
    if i >= n 
    then i 
    else i * loop (i+1) 
    in 
    loop 1 

Dies ist eine Vorwärts-Rekursion ist und wie man sehen kann, ist es etwas umständlicher als die Rückwärts-rekursive Variante, da sie eine Hilfsfunktion erfordert. Nun ist dies nicht tail rekursiv, da der letzte Aufruf in loop die Multiplikation ist, nicht die Rekursion. So machen es Schwanz-rekursiv, Sie so etwas tun würde:

let fac n = 
    let rec loop acc i = 
    if i >= n 
    then acc 
    else loop (i*acc) (i+1) 
    in 
    loop 1 1 

Nun ist dies sowohl eine Vorwärts-Rekursion und eine Endrekursion da der rekursive Aufruf ist a) ein Tail-Call und b) nennt sich mit einem größeren Wert (i+1).

Answer 2

Hier ist ein Beispiel eines Schwanzes rekursiven faktorielle Funktion:

let fac n = 
let rec f n a = 
    match n with 
    0 -> a 
    | _ -> f (n-1) (n*a) 
in 
f n 1 

Hier ist es nicht-tail rekursiven Gegenstück:

let rec non_tail_fac n = 
match n with 
0 -> 1 
| _ -> (non_tail_fac n-1) * n 

Der Schwanz rekursive Funktion eines Akkumulators verwendet, a, zu speichern, die Wert des Ergebnisses des vorherigen Anrufs. Dies ermöglicht es OCaml, eine Tail-Call-Optimierung durchzuführen, die dazu führt, dass der Stapel nicht überläuft. In der Regel verwendet eine rekursive Tail-Funktion einen Akkumulatorwert, um die Tail-Call-Optimierung zu ermöglichen.

Answer 3

Zum Beispiel kann eine rekursive Funktion build_word, die nimmt ein char list und kombiniert sie zu einem String heißt ['f'; 'o'; 'o'] bespannen "foo". Der Induktionsprozess kann auf diese Weise visualisiert werden:

build_word ['f'; 'o'; 'o'] 
"f"^(build_word ['o'; 'o']) 
"f"^("o"^(build_word ['o']) // base case! return "o" and fold back 
"f"^("o"^("o")) 
"f"^("oo") 
"foo" 

Das war eine normale Rekursion. Beachten Sie, dass jedes Klammerpaar für einen neuen Stapelrahmen oder einen rekursiven Aufruf steht. Die Lösung für dieses Problem (d. H. "F", "fo" oder "foo") kann nicht vor dem Ende der Rekursion (wo der Basisfall erfüllt ist) abgeleitet werden. Nur dann gibt das letzte Bild das letzte Ergebnis zurück zum vorherigen, bevor es "poppt", und umgekehrt.

Theoretisch erstellt jeder Aufruf einen neuen Stapelrahmen (oder Bereich, wenn Sie so wollen), um den "Platz" für die fragmentierte Lösung zu behalten, die zurückgegeben und zu Beginn gesammelt wird.Dies kann zu stackoverflow führen (dieser Link ist eine Rekursion btw).

Ein Endrekursion Version würde wie folgt aussehen:

build_word ['f'; 'o'; 'o'] "" 
build_word ['o'; 'o'], "f" 
build_word ['o'] ("f"^"o") 
build_word [] ("f"^"o"^"o") 
"foo" 

Hier wird das akkumulierte Ergebnis (oft in einem als accumulator bekannten Variable gespeichert) geleitet vorwärts wird. Bei der Optimierung müsste Tail Call keinen neuen Stack-Frame erstellen, da die vorherigen nicht beibehalten werden müssen. Die Lösung wird "vorwärts" anstatt "rückwärts" gelöst.

Hier sind die build_word Funktionen in zwei Versionen:

nicht-Schwanz

let build_word chars = 
    match chars with 
    | [] -> None 
    | [c] -> Some Char.to_string c 
    | hd :: tl -> build_word tl 
;; 

Schwanz

let build_word ?(acc = "") chars = 
    match chars with 
    | [] -> None 
    | [c] -> Some Char.to_string c 
    | hd::tl -> build_word ~acc:(acc^Char.to_string hd) tl 
;; 

Die Vorwärtsrekursionsarithmetikeinheiten in der akzeptierte Antwort gut erklärt von @ sepp2k.