Beim Spielen mit einem Tail-Recursion-Beispiel habe ich eine kleine Diskrepanz zwischen den Ergebnissen eines normalen rekursiven Aufrufs und eines rekursiven Tail-Aufrufs festgestellt:
%Vor% Nur aus Neugier, kann mir bitte jemand erklären, warum oder wo die Rundung stattfindet. Meine Vermutung ist, dass, weil der Scala-Compiler die rekursive Tail-Version in eine Schleife übersetzt, der acc -Parameter bei jeder Iteration der Schleife zugewiesen wird, und dass der kleine Rundungsfehler dort hineinrutscht.
Das Ergebnis ist anders, weil die zwei Versionen die Multiplikationen in unterschiedlicher Reihenfolge ausführen, was zu unterschiedlichen Rundungen führt.
Der normale rekursive Aufruf führt zu einem Ausdruck n*([n-1]*([n-2]*(...))) , weil Sie zuerst den Wert von fact (n-1) berechnen und ihn dann mit n multiplizieren, während der rekursive Tail zu ((n*[n-1])*[n-2])*... führt, weil Sie zuerst mit multiplizieren n und dann auf n-1 iterieren.
Versuchen Sie, eine der Versionen neu zu schreiben, so dass sie anders herum iteriert und Sie theoretisch die gleiche Antwort erhalten sollten.
Ihre zwei Funktionen führen die Operationen nicht in der gleichen Reihenfolge durch.
In C:
%Vor%druckt:
%Vor%(Ich habe eine Plattform benutzt, auf der Gleitkomma in C vorhersagbar funktioniert)
Eine Version Ihrer Funktion berechnet 30.*29*... und die andere berechnet 2.*3*... .
Es ist normal, dass diese beiden Ergebnisse leicht unterschiedlich sind: Fließkommaoperationen sind nicht assoziativ. Aber bitte beachten Sie, dass die Ergebnisse nicht unergründlich sind. Eine Ihrer Funktionen berechnet genau den IEEE 754-Ausdruck mit doppelter Genauigkeit 30.*29*... und der andere berechnet genau 2.*3*... . Beide funktionieren wie geplant.
Wenn ich raten müsste, würde ich erwarten, dass 2.*3*... genauer ist (näher an dem mit reellen Zahlen erzielten Ergebnis), aber das spielt keine Rolle: Die beiden Zahlen sind sehr nah und sehr nah am realen Ergebnis.
Der Unterschied liegt nicht darin, dass Scala die Tail-Rekursion in eine Schleife verwandelt. Ohne diese Optimierung wäre das Ergebnis dasselbe. Auch die Rekursion verhält sich in Bezug auf Rundungsfehler nicht anders als Schleifen.
Der Unterschied ist die Reihenfolge, in der die Zahlen multipliziert werden. Ihre erste Lösung wird bis auf 1 zurückgespielt, bevor sie mit der Multiplikation der Zahlen beginnt. Es wird also am Ende n * ( (n - 1) * (... * (2 * 1))) berechnen. Die rekursive Version des Tails beginnt sofort mit der Multiplikation, also berechnet sie n * (n-1) * ... * 2 * 1 .
Natürlich würden wir normalerweise sagen, dass diese beiden identisch sind, weil die Multiplikation assoziativ ist, aber das gilt nicht für Fließkomma-Arithmetik. Die Verwendung von Gleitkommawerten (x * y) * z kann sehr wohl von x * (y * z) abweichen, da sich Rundungsfehler anders ausbreiten. Das erklärt dein Verhalten.
Beachten Sie, dass Sie den gleichen Unterschied sehen werden, wenn Sie eine for-Schleife verwenden, die von 1 bis n zählt und von 1 bis n zählt, um die Fakultät zu implementieren.
Tags und Links scala