2012-04-11 7 views
2

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-Warum die tail rekursive Funktion für eine Eingabe fehlschlägt, für die die normale rekursive Funktion erfolgreich ausgeführt wird?

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?

+3

Ich glaube, dass Sie etwas falsch verstehen - die Verwendung eines Akkumulatorarguments macht eine Funktion nicht tail-rekursiv. Ein Akkumulatorargument ist eine Technik zum Akkumulieren von Werten, wenn eine tailrekursive Funktion verwendet wird. Es ist eine Art von Technik, die normalerweise mit Tail-Recursive kommt, aber nicht Tail-Recursive definiert. –

Antwort

10

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.

+0

das ist richtig, aber ich kann es nicht richtig markieren (noch 6 Minuten zu gehen). Was für ein Unterschied macht das? – Kapil

+2

Der Operator '+' muss auf einen Rückgabewert von loop angewendet werden, sodass der Compiler keine Tail-Rekursion verwenden kann, die den Status von h für jeden rekursiven Aufruf vergessen würde. Die Tail-Rekursion funktioniert, wenn der Status vergessen werden kann - wenn wir wissen, dass der Rückgabewert sonst durch alle Stack-Frames unverändert zurückgegeben würde. –