Warum die tail rekursive Funktion für eine Eingabe fehlschlägt, für die die normale rekursive Funktion erfolgreich ausgeführt wird?

Question

Wie in der Dokumentation MSDN, beim Schreiben rekursiver Funktion, Die Verwendung des Akkumulator-Arguments macht die Funktion Tail rekursiv, was Stapelspeicher spart. ich zwei Beispiel auf der MSDN-Website gegeben mit berechnen der Summe aller Zahlen in einem Listen-

zuerst ohne Schwanz recursion-

let rec Sum myList = 
    match myList with 
    | [] -> 0 
    | h::t -> h + Sum t 

und jetzt mit Schwanz recursion-

let Sumtail list = 
    let rec loop list acc = 
     match list with 
     | h::t -> loop t acc + h 
     | [] -> acc 
    loop list 0 

und beide Funktionen mit dem Eingang [1..100000] ausführen. Funktion Sum berechnet erfolgreich die Summe dieser Liste, gibt aber stackoverflow Ausnahme, wenn ich [1..1000000] übergebe aber die zweite Funktion Sumtail schlägt bei [1..100000] fehl, während es bessere Leistung als die erste Funktion geben sollte, da es Tail-Rekursion verwendet. Gibt es weitere Faktoren, die die rekursive Funktion beeinflussen?

Answer 1

Ihre zweite Funktion ist nicht Schwanz-rekursive seit loop t acc + h als (loop t acc) + h analysiert wird, die die letzte Operation auf loop+ werden läßt.

Ändern Sie loop t acc + h in loop t (acc + h), damit die Funktion tail-rekursiv wird.