Rekursiv vs. Iterativ

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:

Factorial recursive and iterative
---------------------------------

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.

Factorial Source Code

2 Gedanken zu „Rekursiv vs. Iterativ

  1. Roland Bär Beitragsautor

    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.

    Antworten
  2. Pingback: Rekursiv vs. Iterativ revisited | of bits and bytes

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.