3. Stilfrage: Iteration in Rekursion ?

Stilfrage: Iteration in Rekursion ?

  • D

    Also ich glaube, wir haben vor ca 2 Jahren mal eine tiefgreifende Diskussion zu dem Thema gehabt..
    Rekursion ist leider nicht besonders beliebt - was ich schade finde - aber zur Frage : Es kommt auf die schleife an. Wenn diese Schleife nichts mit der eigentlichen Rekursion zu tun hat - oder diese ersetzt, ist es durchaus kein Problem. Nur ist es etwas sinnlos, wenn die Schleife durch etwas Programmierung in die Rekursion einfließen würde.

    0
  • O

    Erhard Henkes schrieb:

    Man sollte es vermeiden, falls möglich, ist aber keine Stilfrage.

    allgemein:
    http://www.educeth.ch/informatik/leitprog/rekursion/docs/rekursion.pdf

    ich würde sagen das hat mit dem Einsatzgebiet zu tun. Es wäre unsinnig als for-Schleifenersatz ne rekursion einzubauen aber versuch doch mal nen Parser mit einer definierten Gramatik zu bauen ohne rekursion. 👎

    0
  • B

    Online schrieb:

    versuch doch mal nen Parser mit einer definierten Gramatik zu bauen ohne rekursion. 👎

    yacc

    0
  • O

    Superbeitrag...4 Buchstaben sind auch eine Zeichenkette ja...stimmt

    glich von vorne weg...ich hab nicht gesagt das es nicht möglich ist
    das 👎 soll heißen ist schlecht, umständlich, zeitaufreibend usw...

    0
  • R

    Online schrieb:

    Superbeitrag...4 Buchstaben sind auch eine Zeichenkette ja...stimmt

    glich von vorne weg...ich hab nicht gesagt das es nicht möglich ist
    das 👎 soll heißen ist schlecht, umständlich, zeitaufreibend usw...

    reg dich ab: YACC ist ein Compilertool. Sogar ziemlich bekannt
    http://dinosaur.compilertools.net/
    http://www.epaperpress.com/lexandyacc/
    ...

    0
  • B

    kingruedi schrieb:

    YACC ist ein Compilertool.

    Eins ohne Rekursion, möchte ich noch hinzufügen. Aber ich dachte eigentlich, jemand der Parserbau als Argument anführt wüßte zumindest was yacc ist 😕

    0
  • S

    Seinem Beitrag zufolge denke ich er weiß, was yacc ist.

    Nur die Existenz muß halt nich bedeuten, daß es auch "schön" bzw. praktisch ist...

    0
  • B

    Dann hätte er nicht so scharf reagiert.

    0
  • O

    Bashar schrieb:

    Dann hätte er nicht so scharf reagiert.

    ich hab nicht scharf reagiert...mir ist sehr wohl klar das es auch ohne rekursion geht, jedes rekursive Problem läßt sich auch interativ lösen. Die andere Frage ist, was bringt es?
    Rekursiv ist viel eleganter und vor allem meistens extrem kürzer.

    übrigens hab ich auch was von einer Grammatik geschrieben. Terminalsymbol/Nichtterminalsymbol...also wenn sich da nicht die rekursion anbietet.

    0
  • S

    Online schrieb:

    Die andere Frage ist, was bringt es?

    Performanz u.U. 💡

    0
  • R

    @Online
    YACC erzeugt dir aus einer gegebenen Gramatik einen Parser der nicht rekursiv ist. Das ist der ganze Punkt an Bashars "4 Buchstaben" 🙂 Und das geht sicher schneller, als sich die Gramatik per Hand in eine Rekursion umzuformen 😉

    0
  • W

    Online schrieb:

    Rekursiv ist viel eleganter und vor allem meistens extrem kürzer.

    Rekursion birgt viele Gefahren. In vielen Fällen macht es eben doch Sinn die iterative Lösung zu bevorzugen, auch wenn sie nicht die Eleganteste ist.

    0
  • B

    MaSTaH schrieb:

    Rekursion birgt viele Gefahren.

    Dann nenn mal 2 🙂

    0
  • S

    - Endlosrekursion weil man zu dumm war korrekte Abbruchbedingen einzuführen
    - Stack-Overflow weil die Funktion zu oft aufgerufen wird

    MfG SideWinder

    0
  • R

    SideWinder schrieb:

    - Endlosrekursion weil man zu dumm war korrekte Abbruchbedingen einzuführen

    Das gibt es ja auch beim iterieren und sollte man spätestens beim testen merken.

    0
  • S

    kingruedi schrieb:

    Das gibt es ja auch beim iterieren

    Hat ja keiner anders behauptet 😉

    MfG SideWinder

    0
  • O

    Sgt. Nukem schrieb:

    Online schrieb:

    Die andere Frage ist, was bringt es?

    Performanz u.U. 💡

    da ist es schon wieder, das Einsatzgebiet zählt. Was ist mit quicksort? Mergesort? Die benutzen alle Rekursion und was die Performanz angeht 👍

    SideWinder schrieb:

    - Endlosrekursion weil man zu dumm war korrekte Abbruchbedingen einzuführen
    - Stack-Overflow weil die Funktion zu oft aufgerufen wird

    MfG SideWinder

    also beide Argumente haben nicht viel mit dem Verfahren zu tun

    Punkt 1 -> eindeutig die Pflicht des Programmierers. hat nichts mir rekusion zutun. Wenn du dir genau überlegst was general case und was base case ist dann hast du's schon so gut wie gelößt.

    Punkt 2 -> man muss ja nicht unbedingt mit der Rekursion übertreiben. Du hast ein Problem und du überlegst dir die Lösung. Darum geht es, immer und immer wieder. Liegt nicht am Verfahren sondern am Programmierer. Hast du das Problen, das dein Stack überläuft dann überlege dir was du machst. Interativ oder doch Stack größer machen.

    0
  • O

    kingruedi schrieb:

    @Online
    YACC erzeugt dir aus einer gegebenen Gramatik einen Parser der nicht rekursiv ist. Das ist der ganze Punkt an Bashars "4 Buchstaben" 🙂 Und das geht sicher schneller, als sich die Gramatik per Hand in eine Rekursion umzuformen 😉

    warum geht das schneller? Wenn ich die Gramatik hab dann brauch ich nicht mit zwang die Gramatik rekursiv zu machen, entweder sie ist schon Rekursiv oder du hast nichts rekursives in der Gramtik.

    ein kleines Beispiel: HTML-Parser
    du willst prüfen ob dein Code richtig ist.

    es wird ein Starttag erwartet. Jedem Starttag folgt ein Endtag. Dazwischen kann, muss aber nicht wieder ein Starttag/Endtag -Konstrukt liegen. Du sollst natürlich auch die Namen des Endtags mit dem dazu passenden Starttag überprüfen.
    Der eine Programmiere führt intern zwei Stacks um die Namen zu speichern (oder wie auch immer) der andere macht ne rekursion draus und gibt einfach den Namen in der Funktion zurück.

    EDIT: übrigens würde sich hier automatisch in der Gramatik eine rekursion ergeben

    Wie immer ist das Einsatzgebiet entscheident und nicht der Geschmack.

    0
  • S

    Online schrieb:

    Sgt. Nukem schrieb:

    Online schrieb:

    Die andere Frage ist, was bringt es?

    Performanz u.U. 💡

    da ist es schon wieder, das Einsatzgebiet zählt. Was ist mit quicksort? Mergesort? Die benutzen alle Rekursion und was die Performanz angeht 👍

    Ich kann MergeSort auch problemlos bottom-up (iterativ) implementieren?!? 😕

    Der Vorteil ist, daß nicht dauernd Funktionsparameter auf den Stack gepopt und gepusht werden müssen... 👍

    0
  • O

    Sgt. Nukem schrieb:

    Ich kann MergeSort auch problemlos bottom-up (iterativ) implementieren?!? 😕
    Der Vorteil ist, daß nicht dauernd Funktionsparameter auf den Stack gepopt und gepusht werden müssen... 👍

    ist klar das du MergeSort interativ lößen kannst...den jedes rekursive Problem kann interativ gelößt werden (nach meinem Wissenstand)

    ist klar das jeder Funktionsaufruf Stackarbeit erfordert. Du kannst aber nicht pauschal sagen das Rekursion mehr Systemarbeit braucht als die Interative lösung.
    Ich weis nciht ob z.B. die interative Lösung von Quicksort schneller ist. Ehrlich gesagt will ich mir den Code dafür garnicht vorstellen.

    Wenn es um die fibonacci- Zahlen geht dann würde ich sagen Interativ ist eindeuig schneller, dafür ist die rekursive Lösung 3 zeilen lang. Mehr als 40 Zahlen merkt man Interativ aber schon deutlich im Zeitverhalten.

    0
Anmelden zum Antworten