Wo braucht man Rekursion, beim Programmieren?
Wenn ich eine Fakultätsfunktion mit Rekursion programmiere ist es bei kleinen n ungefähr so schnell wie eine selbst programmierte Iterative Fakultätsfunktion... Nur wenn das n größer also so 400 wird, dann wird es natürlich messbar langsamer als die Iterative Funktion.
Nun meine Frage: wo braucht man realistisch Rekursion in der Programmiertechnik?
LG
5 Antworten
Ständig, wenn es darum geht, baumartige Strukturen zu durchlaufen. Oder schnell zu sortieren. Oder einfach immer dann, wenn eine schicke Rekursion viel eleganter ist, als ein ewig langer iterativer Algorithmus.
Es ist nicht langsamer - zumindest nicht immer. Zumindest gibt es erstmal keinen Grund, warum das so sein sollte.
Echt nicht...? Was ist dann mit meiner Fakultätsfunktion? Im Durschnitt ist sie um 0.00011s (gemessen) langsamer als bei der Iterativen Lösung
Kommt ja darauf an, wie Du sie programmiert hast. Und 0.00011s kannst Du an einem normalen Windows PC gar nicht messen. So genau löst das gar nicht auf ;-) Mal abgesehen davon, dass 0.00011s vernachlässigbar sind. Je komplexer der Algorithmus iterativ ist, desto mehr geht das Pendel in Richtung Rekursion
Ähm doch...xD Mit python... ich habe es mit dem "time" Modul gemacht und es ist sogar noch viel genauer xD
bei meinen Windows 10 PC: 20 Stellen nach dem Komme, so genau
OK, ich war bei Timer-Auflösung. Da kann Windows nur höchstens 18ms auflösen - zumindest war es immer mal so. Sei's drum.
Nehmen wir an, Du kannst wirklich so genau messen und hast eine repräsentative Messung gemacht (Also beispielsweise 100.000 mal rekursiv vs. 100.000 mal iterativ und das dann gemittelt), ist immernoch der Fak-Algorithmus iterativ so simpel, dass der Aufwand für die rekursiven Aufrufe eventuell höher ist.
Programmiere mal einen Quicksort sowohl rekursiv als auch iterativ und dann miss nochmal.
Dacht ich mir schon...
Programmiere mal einen Quicksort sowohl rekursiv als auch iterativ und dann miss nochmal.
Muss ich mal ausprobieren
Langsamer oder nicht langsamer ist immer eine Frage dessen wie komplex der Algorithmus wird.
Wenns einfache Algorithmen sind die Iterativ sehr schön dargestellt werden können wie die Berechnung einer Fakultät sind die Iterativen Verfahren viel schneller weil eben der komplette Overhead für den Funktionsaufruf wegfällt.
Zudem sind iterative Algorithmen weniger Speicheraufwändig.
Wenns hingegen darauf hinaus läuft, dass der Iterative Algorithmus extrem komplex wird im Vergleich zum Rekursiven hat der Rekursive die Nase vorn.
Btw Python ist aber mit dem normalen Python Interpreter genau genommen auch schon von sich aus sehr langsam, der gibt dir eben schon alleine deswegen einen größen Overhead für Funktionsaufrufe usw mit als zB C das macht. In C++ besteht zudem die Möglichkeit mittels Template Meta Programming Rekursive Funktionen komplett aufzulösen sofern zur Kompile Time bekannt ist wie oft diese Aufgerufen werden. Da dir dann der Kompiler bereits die Rekursion auflöst hat das auch gar keinen Einfluss auf die Laufzeit mehr.
Wo Algorithmen rekursiver Natur sind, sollten sie unbedingt auch rekursiv notiert werden: Alles andere wäre deutlich umständlicher (und deswegen weniger wertvoller Code).
Du brauchst nicht unbedingt Rekursion, es ist manchmal einfach nur der einfachste Lösungsweg.
Das muss man manchmal einfach als Entwickler abschätzen ob es sinnvoll ist oder nicht.
Ich musste mal stark verschachtelte Daten verarbeiten und da war Rekursion eben der offensichtlichste Weg. Hätte ich da mit Schleifen gearbeitet wäre es einfach ein komplexerer und unübersichtlicherer Lösungsweg geworden. Performance war mir in dem Moment gar nicht mal wichtig.
Überall dort, wie sie die naheliegende Umsetzung sind und die Performance hinreichend gut ist.
Insbesondere bei Rekursiven Strukturen, bietet sich die Rekursion an, um entsprechende Probleme zu lösen.
Bei Divide an Conquer bietet sich auch oft eine Rekursion an.
Ich hatte heute ein Beispiel für einen anderen Fragesteller. Er wollte Stirlingzahlen berechnen.
https://de.wikipedia.org/wiki/Stirling-Zahl#Eigenschaften_2
Die rekursive Formel ist schön einfach, bei der expliziten Formel würde man sich einen Wolf programmieren.
Kann ich verstehen dass das schicker ist xD Aber es ist sicherlich bei großen Strukturen langsamer als was iteratives, warum benutzt man es dann überhaupt, gerade dann wenn es um Schnelligkeit geht?