3. Stilfrage: Iteration in Rekursion ?

Stilfrage: Iteration in Rekursion ?

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

    Ich arbeite auch oft rekursiv. Aus Geschwindigkeitsgründen gewisse Dinge iterativ lösen kann ich immernoch.

    Man darf sich vorher niemals überlegen, mach ich das jetzt rekursiv oder iterativ, sondern überlegt sich einfach, wie man sich den Algorithmus vorstellt. Dabei hat man dan automatisch entweder einen rekursiven Ansatz oder einen iterativen Ansatz im Kopf und genau so würde ich es dann auch implementieren.

    0
  • O

    Helium schrieb:

    Ich arbeite auch oft rekursiv. Aus Geschwindigkeitsgründen gewisse Dinge iterativ lösen kann ich immernoch.

    Man darf sich vorher niemals überlegen, mach ich das jetzt rekursiv oder iterativ, sondern überlegt sich einfach, wie man sich den Algorithmus vorstellt. Dabei hat man dan automatisch entweder einen rekursiven Ansatz oder einen iterativen Ansatz im Kopf und genau so würde ich es dann auch implementieren.

    genau das sag ich dauernd, Einsatzgebiet zählt und nicht einfach von anfang an sich gegen stellen

    ->>

    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

    0
  • S

    Online schrieb:

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

    Yupp.

    Online schrieb:

    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.

    Habe ich auch gar nicht. Pauschal ohnehin nicht.

    Ich hab' nur einen Grund genannt, warum man Iteration bevorzugen KÖNNTE:

    Performanz u.U. (unter Umständen)!!

    Manchmal ist es auch wichtiger, Codequalität und Wartbarkeit zu erhalten, als 1% mehr Leistung rauszukitzeln.

    Und Probleme, die ursprünglich nach einer Rekursion geradezu schreien, interativ zu lösen, kann auch in 'nem ziemlichen Trauma enden...
    Dann rennt man nur noch mit langem Gesicht herum und spricht kein Wort mehr... 😃

    0
  • W

    Bashar schrieb:

    MaSTaH schrieb:

    Rekursion birgt viele Gefahren.

    Dann nenn mal 2 🙂

    Von typischen Anfängerfehlern wie Abbruchbedingung vergessen/fehlerhaft mal abgesehen:
    - Man kann den Speicherbedarf nicht mehr so einfach à priori schätzen, wie im iterativen Fall.
    - Es kann sein, dass Ergebnisse unnötiger Weise mehrfach berechnet werden. Gut, wenn man schlau ist baut man eine Memoization ein, aber dann sieht die Lösung nicht mehr so elegant aus. Das wurde hier aber anscheinend als großer Vorteil angeführt.

    0
  • B

    MaSTaH schrieb:

    - Man kann den Speicherbedarf nicht mehr so einfach à priori schätzen, wie im iterativen Fall.

    Das gilt aber nicht, wenn der entsprechende iterative Algorithmus auch einen Stack benötigt.

    - Es kann sein, dass Ergebnisse unnötiger Weise mehrfach berechnet werden.

    Dann ist der Algorithmus einfach schlecht. Man kann sicher auch mit Iteration schlechte Algorithmen schreiben.

    0
  • W

    Bashar schrieb:

    MaSTaH schrieb:

    - Man kann den Speicherbedarf nicht mehr so einfach à priori schätzen, wie im iterativen Fall.

    Das gilt aber nicht, wenn der entsprechende iterative Algorithmus auch einen Stack benötigt.

    Ist aber nicht immer so. Ansonsten ACK.

    0
Anmelden zum Antworten