3. Stilfrage: Iteration in Rekursion ?

Stilfrage: Iteration in Rekursion ?

  • 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
  • H

    Wie heißt es doch so schön in Steve McConnells "Code Complete":

    In general, recursion leads to small code and slow execution and chews up stack space. For a small group of problems, recursion can produce simple, elegant solutions. For a slightly larger group of problems, it can produce simple, elegant, hard-to-understand solutions. For most problems, it produces massively complicated solutions[...]. Use recursion selectively.

    Den "general case" sieht man immer wieder an Beispielen wie rekursive Berechnung von Fibonacci-Zahlen bzw. der Fakultät (ein anderes Beispiel, dass ich letztens hatte: Wildcard-Matching (* und ? als Wildcards). Rekursiv gelöst schön kurz (4-5 Zeilen) und im Vergleich zur iterativen Lösung *richtig* langsam).
    Die "hard-to-understand"-Geschichte ist imo auch nicht zu unterschätzen. Rekursion gehört imo eindeutig zu den Sachen, die sich leichter schreiben als lesen lassen. Das gilt zumindest für den Durchschnittsprogrammierer der nicht täglich Rekursion benutzt. Schwer zu verstehen heißt immer auch schwer zu warten.
    Rekursion hat definitv seine Anwendungsgebiete. Im Allgemeinen würde ich allerdings eher zu einer "lieber-einmal-zuwenig-als-einmal-zuviel"-Strategie raten. Besonders wenn man in einem Team arbeitet, zu dem auch Leute mit kleinen Gehirnen (also Leuten wie ich) gehören.

    0
  • J

    HumeSikkins schrieb:

    Rekursion gehört imo eindeutig zu den Sachen, die sich leichter schreiben als lesen lassen.

    Das stimmt. Deswegen baue ich oft ne rekursive Variante, weil mir die iterative zu kompliziert ist. Dann versuche ich ne Restrekursive Funktion draus zu machen und danach mach ich's iterativ. Man kann sich oft viele Schlaue Ideen bei der Rekursion holen, aber wirklich implementieren tut man's dann doch iterativ.

    Beispiel:

    int pow(int a, int b)
{
  if(b==0) return 1;
  if(b%2==0) return sqr(pow(a,b/2));
  return a*pow(a,b-1);
}

    ist einfach genial. Man sieht genau was gemacht wird. (Zumindest wenn man's selber geschrieben hat). Und der Trick ist wirklich gut. Aber dennoch möchte man nicht ständig die Funktionsaufrufe zahlen. Also implementiert man das ganz iterativ, merk sich aber den Trick.

    Mir jedenfalls fällt es vielen Problemen deutlich leichter den rekursiven Algo zu finden. Quicksort rekursiv, kein Problem... iterativ? Naja, denke ich würd's hinkriegen, macht aber nicht so viel Spaß 😉

    MfG Jester

    0
Anmelden zum Antworten