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:
---------------------------------
10!
Recursive: 00:00:00.0390023
Iterative: 00:00:00.0220012
100!
Recursive: 00:00:00.2940168
Iterative: 00:00:00.1720099
1000!
Recursive: 00:00:02.5131437
Iterative: 00:00:01.0270588
10000!
Recursive: 00:00:25.0624335
Iterative: 00:00:09.4535407
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.
Noch zwei Anmerkungen:
1. Ein weiterer Grund für die iterative Variante ist die bessere Parallelisierbarkeit, die bei den neuen Prozessoren mit mehreren Kernen immer wichtiger wird.
2. Es ist mir klar, dass mein Code keine gültigen Resultate liefert, wenn eine Fakultät > 12! berechnet wird, da der int dann überläuft. Ich habe das in Kauf genommen, da mich nur das Laufzeitverhalten interessierte und der Fehler in beiden Varianten auftritt.
Pingback: Rekursiv vs. Iterativ revisited | of bits and bytes