Rekursion vermeiden... Wieso?

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

knivil

Bashar schrieb:

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

Ja, das war meine Grundlage. Ich haette auch darauf verlinkt, aber konnte es irgendwie finden.

@Jester: Da stimmme ich dir zu. Dem entgegenhalten wuerde ich, dass es eine eher ungluecklich implementiert ist. Man kann immer irgendwelchen Bloedsinn machen. Auch hat hustbaer auf das Problem aufmerksam gemacht, aber ich weiss es nicht genau in Worte zu fassen.

frosch03

Also ich würde sagen, etwas ist Rekursiv, wenn es sich auf sich selber bezieht.

Ob das jetzt eine Funktion, ein Datentyp oder die natürlichen Zahlen sind, ist
erstmal egal.

Beschränkt man sich auf rekursive Funktionen, und möchte verstehen warum es
Leute gibt, die das vermeiden, muss man verstehen was Rekursion bedeutet.

Im Computer wird ein Funktionsaufruf mithilfe von einem Stack gemacht. Dieser
wird genutzt, um:
* die Parameter an die nächste Funktion zu übergeben,
* die Rücksprungadresse der alten Funktion zu sichern,
* die Adresse des Stackframes zu sichern,
* vielleicht noch was?

Hat man jetzt eine Funktion, die sich selber aufruft, wächst mit jedem
Funktionsaufruf der Stack an. Da der Stack nicht unendlich ist, kann es sein,
dass irgendwann der Platz nicht mehr ausreicht und das Programm abstürzt.

Kann man dieses Problem vermeiden? Ja, mithilfe von Tail-Rekursion.
Das bedeutet, dass der rekursive Aufruf immer die letzte Anweisung der Funktion
ist. Der Vorteil liegt darin, dass der Compiler einen solchen Funktionsaufruf
in einen "Sprung" an den Funktionsanfang auflösen kann.

Dass bedeutet nun, dass der Stack nicht anwächst und so auch nicht überlaufen
kann.

Ich denke daher, Rekursion zu verbieten ist ganz sicher der falsche Ansatz.
Denn man verbietet ein sehr elegantes Abstraktionswerkzeug. Und das führt
sicher zu viel größeren Problemen.

Allerdings ist es auch wichtig, dass man versteht, wann ein rekursiver Aufruf
Probleme bereiten kann.

Also Rekursion nicht verbieten, sondern aufklären!

grüße,
frosch

knivil

Also ich würde sagen, etwas ist Rekursiv, wenn es sich auf sich selber bezieht.

Ja, aber nicht nur, wie der Y-Kombinator zeigt.

Rekursion zu verbieten ist ganz sicher der falsche Ansatz

Wer will das denn?

volkard

knivil schrieb:

Rekursion zu verbieten ist ganz sicher der falsche Ansatz

Wer will das denn?

Es gibt immer wieder solche Forderungen. Und es gibt immer Unternehmen, die Rekurson verbieten. Sogar große wie die Deutsche Bahn sind davor nicht gefeit.

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.

Bashar

Das ist "Rekursion in C und C++", was da verboten ist. In Sprachen, in denen ein Stack-Overflow genauso zuverlässig abgefangen werden kann wie eine fehlgeschlagene Speicheranforderung, ist das Argument nicht gültig.