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:
-------------------------------------------
10!
Recursive: 00:00:00.1390079
Iterative: 00:00:00.1190069
100!
Recursive: 00:00:01.9631122
Iterative: 00:00:01.7991029
1000!
Recursive: 00:00:51.7689611
Iterative: 00:00:43.3274782
10000!
Process is terminated due to StackOverflowException.
Es sind zwei Dinge ersichtlich:
- 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.
- 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.
Keep in mind that when you write an article you have to keep the audience in mind. Creating a simplistic recursive function to solve a factorial problem displays an easy example for readers to understand. I do believe that he probably should directly cite within the example it is a bad idea for implementation. Not really a big deal though. Good work on the article.