Im KaffeeKlatsch vom November 2012 habe ich einen interessanten Artikel über die Fakultätsberechnung gelesen.

Dies hat mich dazu bewogen, meine eigene Untersuchung nochmals hervorzuholen und zu überprüfen.

Ich habe dabei, wie im KaffeeKlatsch-Artikel, den Datentyp BigInteger (Namespace System.Numerics, Assembly System.Numerics.dll) eingesetzt. Ich habe auch noch die Schlaufe verkürzt, damit ich nicht so lange auf das Resultat warten muss. Weitere Optimierungen habe ich nicht vorgenommen.

Hier das Ergebnis:

Es sind zwei Dinge ersichtlich:

1. Die iterative Implementierung ist immer noch schneller als die rekursive, aber der Unterschied ist nicht mehr so gross. Dies dürfte darauf zurückzuführen sein, dass die eigentliche Berechnung (das Multiplizieren) mit dem BigInteger mehr Aufwand verursacht und der Overhead des rekursiven Aufrufs nicht mehr so ins Gewicht fällt. Dafür spricht auch, dass ich die Wiederholungszahl verkleinern musste.
2. Es wird schon früher eine StackOverflowException geworfen. Dies dürfte auch daran liegen, dass mit dem BigInteger noch weitere Funktionsaufrufe einhergehen, die auf dem Stack gespeichert werden.

Fazit:
Meine erste Untersuchung wurde (ansatzweise) bestätigt, die Vereinfachung mit dem akzeptieren eines falschen Resultates mit dem int hat aber das Ergebnis stärker beeinflusst, als ich das vermutet hatte.

Factorial2 Source Code

In der dotnetpro 8/2011 hat Ralp Westphal im Artikel „Aus Baum mach Fluss“ zum Einstieg die Fakultätsberechnung in der rekursiven und in der iterativen Variante gezeigt. Seiner Meinung nach ist die iterative Variante einfacher zu verstehen, besonders für nicht-Mathematiker.
Ich fragte mich dann, welche Variante ist für den Computer einfacher zu verstehen, d.h. welche Variante ist performanter? Oder ist es egal, optimiert der Compiler schon so weit, dass beide Varianten in etwa gleich schnell sind?

Ich habe ein kleines Programm geschrieben, dass die Fakultät für verschiedene Werte mehrmals berechnet, um messbare Werte zu erhalten.
Hier die Resultate:

Die rekursive Variante braucht also etwa 2.5 mal so lang wie die iterative. Und bei grossen Fakultäten kommt noch ein weiteres Problem hinzu: Es wird eine StackOverflowException geworfen, da jeder Rekursionsschritt einen Funktionsaufruf zur Folge hat, der einen Teil des Stacks beansprucht.

Fazit:
Der iterative Ansatz ist (mindestens in diesem Fall) auch für den Computer „einfacher zu verstehen“. Neben der besseren Performance ist aber auch die gebannte Gefahr des Stack Overflows ein wichtiger Grund, die iterative Varinate vorzuziehen.

Factorial Source Code