Rekursion vermeiden... Wieso?
-
Man sollte dort optimieren, wo es Sinn macht.
Wenn man sieht dass man in einer bestimmten Funktion, die Rekursion verwendet, viel Zeit verbrät, dann kann man ja mal probieren die umzubasteln, und zu sehen, ob man damit was rausholen kann.
Grundsätzlich zu sagen "Rekursion ist Böse weil (tendenziell) langsam", ist IMO doppelt falsch. Erstmal macht es keinen Sinn etwas zu optimieren was "schnell genug" ist, und zweitens kann man garnicht so ohne weiteres sagen, ob eine Funktion wirklich schneller laufen würde, wenn man die Rekursion rausprogrammiert.
Was Tree-Traversal angeht könnte ich mir vorstellen, dass ein Faktor hier einen minimalen Geschwindigkeits-Boost bringt: wenn man in einem Baum nur was sucht, dann muss man, sobald man es gefunden hat, den selbst-verwalteten Stack nichtmehr Stück für Stück "abbauen", sondern kann ihn gleich als ganzes wegwerfen.
BTW: wer versucht Rekursion durch einen Stack zu ersetzen, und dann der Einfachkeit halber einen std::vector<> als Stack verwendet, der wird sein blaues Wunder erleben.
Natürlich nur wenn er sich die Mühe macht, dann auch zu checken, wieviel schneller die Variante mit dem std::vector<> dann ist. (Bzw.: wie viele hundert mal langsamer
)
-
Rekursion kann man doch in der Praxis gar nicht einsetzen. Wie will man den möglichen Stackoverflow verhindern?
-
hmmmmmmmm schrieb:
Rekursion kann man doch in der Praxis gar nicht einsetzen. Wie will man den möglichen Stackoverflow verhindern?
wie macht man das in quicksort?
-
hmmmmmmmm schrieb:
Rekursion kann man doch in der Praxis gar nicht einsetzen. Wie will man den möglichen Stackoverflow verhindern?
die maximale rekursionstiefe muss bekannt sein, oder eine obergrenze muss festgelegt werden, wenn sehr wenig stackspeicher da ist.
-
Es gibt in C und C++ keinen Weg festzustellen, ob der Stackspeicher ausreicht und es gibt keinen Weg sich von einem Stackoverflow zu retten. Daher ist Rekursion in C und C++ eine potentiell böse Sache und viele Codingguidelines verbieten die Verwendung von Rekursion.
(Aus dem gleichen Grund sind C99-VLAs zB auch gefährlich)
-
rüdiger schrieb:
Es gibt in C und C++ keinen Weg festzustellen, ob der Stackspeicher ausreicht und es gibt keinen Weg sich von einem Stackoverflow zu retten. Daher ist Rekursion in C und C++ eine potentiell böse Sache und viele Codingguidelines verbieten die Verwendung von Rekursion.
Klar, potentiell böse. Wasser ist auch böse (9% der schweizer Selbstmörder nehmen Wasser dafür). Und Rekursion zu bieten ist genauso sinnig, wie Wasser zu verbieten.
-
volkard schrieb:
rüdiger schrieb:
Es gibt in C und C++ keinen Weg festzustellen, ob der Stackspeicher ausreicht und es gibt keinen Weg sich von einem Stackoverflow zu retten. Daher ist Rekursion in C und C++ eine potentiell böse Sache und viele Codingguidelines verbieten die Verwendung von Rekursion.
Klar, potentiell böse. Wasser ist auch böse (9% der schweizer Selbstmörder nehmen Wasser dafür). Und Rekursion zu bieten ist genauso sinnig, wie Wasser zu verbieten.
Ja, ich finde Rekursion auch oft praktisch. Aber ich kann schon verstehen, dass die Embededleute da ein bisschen vorsichtiger sind und MISRA und JSF-Guidelines ua. das verbieten.
-
rüdiger schrieb:
Ja, ich finde Rekursion auch oft praktisch. Aber ich kann schon verstehen, dass die Embededleute da ein bisschen vorsichtiger sind und MISRA und JSF-Guidelines ua. das verbieten.
Und wie werden rekursive Probleme (wie quicksort) dann gelöst? Eine Stack-Struktur zu benutzen schützt einen ja auch nicht davor, dass der Speicher ausgeht.
-
maximAL schrieb:
Und wie werden rekursive Probleme (wie quicksort) dann gelöst? Eine Stack-Struktur zu benutzen schützt einen ja auch nicht davor, dass der Speicher ausgeht.
zum beispiel immer zuerst den kleineren ast verfolgen, und den am funktionsende liegenden größeren ast kann man zur schleife umbiegen. damit hats eine rekursionstiefe von max ld(n), auf einem 32-bitter max 32, und dann kann man sich ausdenken, ob man sich 32 leisten mag.
-
maximAL schrieb:
rüdiger schrieb:
Ja, ich finde Rekursion auch oft praktisch. Aber ich kann schon verstehen, dass die Embededleute da ein bisschen vorsichtiger sind und MISRA und JSF-Guidelines ua. das verbieten.
Und wie werden rekursive Probleme (wie quicksort) dann gelöst? Eine Stack-Struktur zu benutzen schützt einen ja auch nicht davor, dass der Speicher ausgeht.
Wenn malloc/new kein Speicher mehr anfordern können, dann erfährt das das Programm und hat Möglichkeiten darauf entsprechend zu reagieren. Wenn der Stack ausgeht, dann kann man sich davon nicht erholen.
-
Zur Verdeutlichung: quicksort braucht für den rekursiven aufruf zwei zeiger begin/end, eine rücksprungadresse, sind schon 3 zeiger und legen wir noch schäzuingsweise 5 Zeiger dazu. macht 4*8*32=1024 bytes. also ich rechne mit einem stack von 1M und kann mir 1k leisten.
aber vor allem kann man den bedarf abschätzen und icht nicht so hoffnungslos ausgeliefert. man kann begründen, weshalb man an bestimmten stellen die rekursion für sicher hält.
-
Wenn man auf Rekursion und alloca/VLAs verzichtet, dann kann man den Stackbedarf einfach mit statischer Analyse abschätzen. Daher verstehe ich die Beweggründe.
Aber bei "normaler Software" dürfte Rekursion den Vorteil haben, dass der Code so leichter zu verstehen ist, als ein auf Iteration umgefrickelter Algorithmus.
-
rüdiger schrieb:
Aber bei "normaler Software" dürfte Rekursion den Vorteil haben, dass der Code so leichter zu verstehen ist, als ein auf Iteration umgefrickelter Algorithmus.
und schneller.
Außerdem ist die statische Analyse einfach zu schlecht unhd inkomplett, wenn man nicht angeben kann, daß eine bestimmte rekursive Funktion sich maximal 32 mal selber aufruft, oder?
-
Wenn ich euch so zuhöre, frag ich mich, ob es nicht Tools gibt, die die Umwandlung von "rekursiv" zu "iterativ umgefrickelt" automatisch machen. Damit hätte man alle Vorteile.
-
µngbd schrieb:
Wenn ich euch so zuhöre, frag ich mich, ob es nicht Tools gibt, die die Umwandlung von "rekursiv" zu "iterativ umgefrickelt" automatisch machen. Damit hätte man alle Vorteile.
Bei Tailrekursion können einige Compiler (zB der GCC ist da wohl recht gut) das auch automatisch. Aber bei komplizierteren Sachen, wird es recht schwierig, da dies massive Codeänderungen erfordern würde.
volkard schrieb:
Außerdem ist die statische Analyse einfach zu schlecht unhd inkomplett, wenn man nicht angeben kann, daß eine bestimmte rekursive Funktion sich maximal 32 mal selber aufruft, oder?
Ja, leider sind die meisten Entwicklungstools für C bzw. C++ sehr primitiv.
-
BTW: wer versucht Rekursion durch einen Stack zu ersetzen, und dann der Einfachkeit halber einen std::vector<> als Stack verwendet, der wird sein blaues Wunder erleben.
Genau dieser Punkt interessiert mich nun:
Bist du dir ganz sicher, dass ein std::vector soviel langsamer als eine std::list ist? Die erforderliche Kapazität ist ja beim Beginn des Traversals bekannt. Das interne Array muss also nicht mehr wachsen...Nehmen wir einen kompletten Binärbaum der Tiefe 16.
Stack implementiert als Dynamische Array mit einer dynamischen Startkapazität von Baumtiefe-1:
-------------------------------------------------------------------------
1*(new+delete), fertig, temporärer Speicheroverhead während Traversal: 60Bytes bei 32-Bit System, 120Bytes bei 64-Bit System.Stack implementiert als Verkettete Liste:
----------------------------------------
32'768*(new+delete),temporärer Speicheroverhead während Traversal: 60Bytes bei 32-Bit System, 120Bytes bei 64-Bit System.Meine Berechnungen gehen davon aus, dass der unterste Level niemals auf dem Stack liegt.
Gruss Samuel
-
Ishildur schrieb:
BTW: wer versucht Rekursion durch einen Stack zu ersetzen, und dann der Einfachkeit halber einen std::vector<> als Stack verwendet, der wird sein blaues Wunder erleben.
Genau dieser Punkt interessiert mich nun:
Bist du dir ganz sicher, dass ein std::vector soviel langsamer als eine std::list ist? Die erforderliche Kapazität ist ja beim Beginn des Traversals bekannt. Das interne Array muss also nicht mehr wachsen...Wo liest du da was vonwegen std::list raus? Ich meinte std::vector im Gegensatz zu einem Array auf dem Stack.
std::vector wird deswegen langsamer sein als eine rekursive Variante, weil std::vector "new" aufruft, und die rekursive Variante das "einsparen" kann. Und "new" ist teuer. Und genauso ist std::vector langsamer als ein Array auf dem Stack.
-
Sorry, hab noch die Berechnungen verändert, während du am schreiben warst.
Jtzt stimmts hoffentlich
Sorry, war eine reine Mutmassung, hast du natürlich nicht gesagt
Aber das native c-array muss ich doch auch zur Laufzeit allozieren, genauso wie den Vector? Da sollte es doch keinen Unterschied machen?
-
Achja...
Nehmen wir einen kompletten Binärbaum der Tiefe 16.
Stack implementiert als Dynamische Array mit einer dynamischen Startkapazität von 2^Baumtiefe = 65536:
Was willst du denn machen, wo du für jeden Knoten einen Eintrack am Stack bräuchtest? Für einen 16 Ebenen tiefen Baum hast du üblicherweise eine Rekursions-Tiefe von <= 16. Gerade deswegen ist es ja auch kein Problem rekursive Algorithmen zu verwenden.
-
@hustbear
Ja da hast du völlig recht, hab nicht gerade viel überlegt als ich den Eintrag geschrieben hatte und erst nach und nach diese Erkenntniss, als ich nach dem Schreiben weiter über dieses Problem nachdachte
