Rekursion vermeiden... Wieso?

hustbaer

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.

Ishildur

@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

knivil

µ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.

Das ist im Allgemeinen nicht moeglich.

Ishildur

Nun glaube ich, das Ganze zu verstehen. Man könnte für das TreeTraversal ein simples dynamisch alloziertes c-array als Stack benutzen und tauscht, 65'536 Funktionsaufrufe gegen ein einziges new und delete. Das kann IMHO doch eine menge bringen

Jester

knivil schrieb:

µ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.

Das ist im Allgemeinen nicht moeglich.

Warum? Ich hab mal irgendwann gelernt, dass rekursive Berechenbarkeit und while-Berechenbarkeit dasselbe sind, man also jedes Programm als while-Programm und sogar mit nur einer Schleife schreiben kann. Oder spielst Du eher auf Probleme bei der automatischen Umsetzung an? Wenn ja, wo hakt es da genau?

knivil

rekursive Berechenbarkeit und while-Berechenbarkeit dasselbe sind

Weil man einen Stack simulieren kann. Aber dann hat man immer noch einen rekursiven Algorithmus. Gewonnen hat man damit aber noch nichts.

Nexus

Ishildur schrieb:

Aber das native c-array muss ich doch auch zur Laufzeit allozieren, genauso wie den Vector? Da sollte es doch keinen Unterschied machen?

Nein, wenn du das Array auf den Stack legst, reicht eine Stackpointer-Verschiebung, das ist sehr effizient. Bei new muss hingegen zuerst ein freier Speicherbereich auf dem Freestore gesucht und beschafft werden. Dafür hat man damit mehr Flexibilität.

Jester

knivil schrieb:

rekursive Berechenbarkeit und while-Berechenbarkeit dasselbe sind

Weil man einen Stack simulieren kann. Aber dann hat man immer noch einen rekursiven Algorithmus. Gewonnen hat man damit aber noch nichts.

Okay, dann haben wir ein Definitionsproblem. Für mich war Rekursion bis jetzt grundsätzlich damit verbunden, dass eine Funktion sich selbst (möglicherweise über Umwege) aufruft. Jetzt sagst Du, dass der Algorithmus auch dann rekursiv bleibt, wenn sich nichts selber aufruft. Woran machst Du fest wann ein Algorithmus rekursiv ist und wann nicht?

Ishildur

@Nexus
Ja schon, aber dann haben wir das Problem, dass eine gewisse Tiefe des entsprechenden Baumes nicht überschritten werden darf...

knivil

Die Fakultaet wird gern dafuer herangezogen. Dazu mal etwas Code, z.B. in Haskell:

fac' 0 = 1
fac' n = n * fac' (n-1)

Dabei wird die erste Funktion so ausgewertet:

fac' 3
3 * fac' 2
3 * 2 * fac' 1
3 * 2 * 1 * fac' 0
3 * 2 * 1 * 1
3 * 2 * 1
3 * 2
6

Dabei faellt auf, dass der Speicher fuer Zwischenergebnisse waechst (im Verhaeltnis zur Ein- bzw. Ausgabe). Das kann ich natuerlich auch mit while und einem kuenstlichen Stack simulieren. Iterativ ist es damit noch lange nicht, auch wenn while gerne damit assoziiert wird.

fac'' n = helper n 1
    where helper 0 acc = acc
          helper n acc = helper (n-1) (n*acc)

Hier wird helper auch rekursiv aufgerufen, aber insgesamt ist es ein iterativer Prozess. Die Funktion wird wie folgt ausgewertet:

fac'' 3
helper 3 1
helper 2 3
helper 1 6
helper 0 6
6

Dabei waechst der Speicher nicht, sondern ist beschraenkt.

Jester

Sorry, ich finde da die Antwort auf eine Frage nicht. Woran machst Du fest ob ein Algorithmus (oder meinetwegen auch ein Prozess) iterativ oder rekursiv ist?

Wenn Du oben sagst, dass es Sachen gibt, die rekursiv machbar sind, aber iterativ nicht, dann mußt Du doch irgendeinen harten Begriff in der Hand haben, mit dem Du solche Aussagen tätigen kannst. Nur danach frage ich. -- Offensichtlich verbindest Du nämlich mit iterativ/rekursiv andere Begrifflichkeiten als ich. Deswegen komme ich ja auch zu einer anderen Aussage.

knivil

Wenn der benoetigte Speicher fuer Zwischenergebnisse im Vergleich zur Ein- bzw. Ausgabe waechst.

Jester

knivil schrieb:

Wenn der benoetigte Speicher fuer Zwischenergebnisse im Vergleich zur Ein- bzw. Ausgabe waechst.

Okay, verstehe. Das halte ich für keine besonders glückliche Definition, aber das steht ja auf nem anderen Blatt.

edit: nochmal zur Klärung, das heißt ein Algorithmus, der sagen wir quadratischen Speicher (quadratisch in der Eingabegröße) benötigt um als Ergebnis eine Zahl zu berechnen wäre automatisch rekursiv?

knivil

Gegenfrage: Ist die Auswertung der Helperfunktion rekursiv oder eher iterativ. Ich finde schon, dass die Auswertung hier an eine for-Schleife mit Hilfsvariable erinnert. Andererseits kann auch Rekursion herbeigefuehrt werden, ohne das eine Funktion sich selbst aufruft. Siehe http://en.wikipedia.org/wiki/Fixed_point_combinator unter Y combinator.

edit: nochmal zur Klärung, das heißt ein Algorithmus, der sagen wir quadratischen Speicher (quadratisch in der Eingabegröße) benötigt um als Ergebnis eine Zahl zu berechnen wäre automatisch rekursiv?

Nenne doch mal ein Beispiel. Jedoch beachte das nicht nur die Eingabe von Bedeutung ist, sondern auch die Ausgabe. Wenn ich Elemente mit bestimmten Eigenschaften in einem Array suche, dann brauche ich auch Speicher im Sinne der Ausgabe. Das zaehlt natuerlich nicht. Genau wie ich fuer 120! natuerlich mehr Speicher brauche als fuer 120. Es geht mir nur um das zusaetzliche an Speicher. Das ist ja auch der Grund dafuer, warum auf Rekursion meist verzichtet wird.

hustbaer

Es gibt viele Algorithmen deren Bedarf an temporärem Speicher mit der Grösse der Eingabe steigt (ob linear oder logarithmisch oder sonstwie is je egal).
Deswegen würde ich aber noch lange nicht alle solchen Algorithmen als "rekursiv" bezeichnen. Sind sie auch nicht.

Rekursiv ist etwas, wo ich als Teil der Berechnung, exakt die selbe Berechnung für kleinere Teilmengen durchführe, bis ich eine bestimmte Schwelle erreicht habe (wie z.B. dass die Teilmengen auf ein einziges Element zusammengeschrumpft ist).

Ob ich das jetzt mit rekursiven Funktionen mache, oder einem selbst verwalteten Hilfs-Stack, ist eigentlich egal.
Es geht hier aber soweit ich es verstanden habe nicht um rekursive Algorithmen vs. nicht rekursive Algorithmen, sondern um rekursive Funktionen vs. nicht rekursive Funktionen.

hustbaer

knivil schrieb:

Das ist ja auch der Grund dafuer, warum auf Rekursion meist verzichtet wird.

Meinst du nicht eher das ist meist der Grund, warum auf Rekursion verzichtet wird (WENN auf Rekursion verzichtet wird)?

So wie du das formuliert hast, würde es bedeuten, dass kaum jemals irgendwer Rekursion verwendet, weil man eben "meist darauf verzeichtet".

volkard

Ishildur schrieb:

Nun glaube ich, das Ganze zu verstehen. Man könnte für das TreeTraversal ein simples dynamisch alloziertes c-array als Stack benutzen und tauscht, 65'536 Funktionsaufrufe gegen ein einziges new und delete. Das kann IMHO doch eine menge bringen

Hardwarestack ist schneller als Softwarstack. Deswegen bost Du mit dem simulierten Stack langsamer. Ist der Baum auch noch balanciert, hat man sogar die nötige Rekursionstiefenbeschränkung.
Also gehe ich durch den AVL-Baum wohl rekursiv und durch einen Verzeichnisbaum mit simulierter Rekursion.

Jester

knivil schrieb:

edit: nochmal zur Klärung, das heißt ein Algorithmus, der sagen wir quadratischen Speicher (quadratisch in der Eingabegröße) benötigt um als Ergebnis eine Zahl zu berechnen wäre automatisch rekursiv?

Nenne doch mal ein Beispiel. Jedoch beachte das nicht nur die Eingabe von Bedeutung ist, sondern auch die Ausgabe.

Okay, ein doofes Beispiel, aber eines das meine Bedenken gut zeigt. Eingabe sind n Punkte in einem vector und eine Zahl x. Zu beantworten ist die Frage, ob es ein Punktpaar gibt, dessen Abstand größer ist als x.

Meine Implementierung macht nun folgendes: Sie legt eine nxn großes Feld an und schreibt da die paarweisen Abstände rein. Anschließend wird das Maximum des Feldes ausgerechnet und dieses mit x verglichen.

Eingabe hat Größe O(n), Ausgabe O(1), Speicherbedarf O(n^2). Nach meinem Geschmack ist das zwar ne dämliche Implementierung, aber rekursiv ist sie imo nicht.

Jester

hustbaer schrieb:

Rekursiv ist etwas, wo ich als Teil der Berechnung, exakt die selbe Berechnung für kleinere Teilmengen durchführe, bis ich eine bestimmte Schwelle erreicht habe (wie z.B. dass die Teilmengen auf ein einziges Element zusammengeschrumpft ist).

das sehe ich genauso.

Es geht hier aber soweit ich es verstanden habe nicht um rekursive Algorithmen vs. nicht rekursive Algorithmen, sondern um rekursive Funktionen vs. nicht rekursive Funktionen.

Ja, so sah das ursprünglich für mich mal aus. Daher auch der Einwand mit der Äquivalenz von rekursiver und while-Berechenbarkeit.

Bashar

knivil hat seine Definition mit ziemlicher Sicherheit (evtl. indirekt) aus SICP:
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2