1. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies. Weitere Informationen

Rekursion vs. Schleife

Dieses Thema im Forum "OS X-Developer" wurde erstellt von Skeeve, 16.02.07.

  1. Skeeve

    Skeeve Pomme d'or

    Dabei seit:
    26.10.05
    Beiträge:
    3.121
    Hier der Urspungsthread...

    Den Stiefel ziehst aber bitte Du Dir an.

    Unbestritten. Damit ersetzt Du aber nicht die Rekursion durch eine Schleife sondern simulierst eine Rekursion indem Du den Rekursionsimmanenten Stack selbst nachbildest. Somit bist Du immernoch bei einer Rekursion, auch wenn es nichtmehr danach aussieht.

    Kein Problem:

    Code:
    function a( m, n ) {
        if ( m == 0 ) {
            return n+1;
        }
        if ( n == 0 ) {
            return a( m-1, n );
        }
        return a( m-1, a( m, n-1 ) )
    }
     
    Peter Maurer gefällt das.
  2. mullzk

    mullzk Linsenhofener Sämling

    Dabei seit:
    04.01.04
    Beiträge:
    2.529
    easy, ackermann, da muss ich ja nicht einmal überlegen sondern kann einfach abschreiben... (musste mal überlegen, aber für etwas bewahrt man sich ja die lösungen aus den übungen auf ;) )

    Generell gilt (habe ich schnell wieder mal in Schöning, Theoretische Informatik, nachgeschaut):
    Jede Rekursion löst exakt dieselben Probleme wie eine Sprache, die alleine auf Zuweisungen, Aneinander-Reihungen sowie der Steuerung LOOP x1 DO p END basiert, inkl. daraus folgender Makros (wie zB if etc.)
    Jede mü-Rekursion löst exakt dieselben Probleme wie eine Sprache den oben genannten Spezifikationen sowie der Steuerung WHILE x1 != 0 DO p END.

    Falsch, ein Stack ist nicht Rekursionsimmanent. Eine Rekursion basiert auf einem Stack, und die einfachst-mögliche Implementation ist ebenfalls Stack-Basiert, aber auch hier gibt es andere Möglichkeiten. (Es gibt übrigens mehrere Sprachen, die Rekursion schlichtwegs verbieten - sollten die deiner Meinung nach ohne Stack auskommen müssen?)

    Also, die Ackermann-Funktion als WHILE-Programm:
    Code:
    INPUT (x,y);
    INIT (stack);
    PUSH (x, stack);
    PUSH (y, stack);
    WHILE size(stack) != 0 DO {
    	y:= POP(stack);
    	x:= POP(stack);
    	IF x=0 {
    		THEN PUSH(y+1, stack);
    	} ELSEIF y=0 {
    		THEN PUSH(x-1, stack); 
    		PUSH(1,stack);
    	} ELSE {
    		PUSH(x-1, stack); 
    		PUSH(x, stack);
    		PUSH(y-1, stack);
    	}
    }
    result := POP(stack)
    OUTPUT(result)
    
     
  3. Skeeve

    Skeeve Pomme d'or

    Dabei seit:
    26.10.05
    Beiträge:
    3.121
    Damit hast Du aber nicht die Rekursion durch eine Schleife, sondern durch einen Stack und eine Schleife ersetzt.

    Aber da Du ja die Ackermann Funktion kennst, brauchen wir nicht weiter zu diskutieren ;) Korinthenkackerisch habe ich Recht, wenn man es nicht gar so genau nimmt, hast Du Recht. Können wir uns darauf einigen?
     
  4. mullzk

    mullzk Linsenhofener Sämling

    Dabei seit:
    04.01.04
    Beiträge:
    2.529
    mein herz sagt ja zur einigung, mein ewiger rechthaberischer Kopf sagt leider nein. Sorry dafür. Fakt ist und bleibt, dass eine WHILE-Sprache (im Gegensatz zur LOOP-Sprache) Turing-vollständig ist. Vollständig äquivalent zu einer µ-rekursiven Sprache. Stack-kompatibel. Churchsche These.

    Wo ich zur Einigung Hand biete, ist der Umstand, dass man eine Rekursion durch Schleifen und Stack rekonstruieren kann, nicht aber, dass ein Stack exklusiv der Rekursion vorbehalten sei.

    Demonstration eines simplen Stack ohne Rekursion. Der Einfachheit nehmen wir mal an, der Stack sei ein String, jeder Eintrag sei ein String von fixer Länge, die Einträge werden von Links nach Rechts konkateniert.

    |width stack stacklength|

    INIT(stack) {
    stack := ""
    stacklength := 0;
    }

    PUSH(x, stack) {
    stack := stack+x
    stacklength := stacklength + 1
    }

    POP(stack) {
    |newstack result cursor|;
    FOR(cursor=0, i < stacklength -1, cursor=+width) {
    newstack := newstack + subString(stack, cursor, width);
    }
    result = subString(stack, cursor, width);
    stack = newstack;
    stacklength = stacklength -1;
    return result;
    }

    sehe nicht ein, wo da ein Zusammenhang mit Rekursion sein soll...
     
  5. Skeeve

    Skeeve Pomme d'or

    Dabei seit:
    26.10.05
    Beiträge:
    3.121
    Wenn Du das aus meinen Aussagen herausgelesen hast, habe ich mich unklar ausgedrückt. Natürlich ist Rekursion nicht die einzige Möglichkeit, einen Stack zu verwenden. Schön blöde wäre ich. Allerdings (und das meint "rekursionsimmanent") liegt einer Rekursion immer ein Stack (in welcher Implementierung auch immer) zugrunde.
     
  6. newman

    newman Roter Eiserapfel

    Dabei seit:
    02.06.05
    Beiträge:
    1.436
    *unterschreib*
     
  7. .holger

    .holger Geflammter Kardinal

    Dabei seit:
    13.09.04
    Beiträge:
    9.117
    oki eki
     
  8. mullzk

    mullzk Linsenhofener Sämling

    Dabei seit:
    04.01.04
    Beiträge:
    2.529
    ok, alles klar, streitigkeit beendet. wieder freunde? :D
     
  9. Skeeve

    Skeeve Pomme d'or

    Dabei seit:
    26.10.05
    Beiträge:
    3.121
    Ich habe Dich nie als Feind betrachtet.
     
  10. mullzk

    mullzk Linsenhofener Sämling

    Dabei seit:
    04.01.04
    Beiträge:
    2.529
    habe ich auch nicht wirklich so gemeint...

    und weil ich es einfach nicht lassen kann, hier noch die erläuterung meiner aussage im haskell-thread, dass rekursionen _in der praxis_ zT weniger mächtig sind: endlos laufende programme

    void hellohellohello() {
    while (true) do {NSLog(@"HelloWorld\n")};
    }

    void hellohellohelStackOverflow() {
    NSLog(@"HelloWorld\n");
    hellohellohelStackOverflow():
    }

    ssso! :p:D
    alles gute aus dem kalten bern
    mullzk
     
  11. Skeeve

    Skeeve Pomme d'or

    Dabei seit:
    26.10.05
    Beiträge:
    3.121
    Meiner Meinung nach ist das keine sinnvolle rekursive Funktion, da sie keine erreichbare Abbruchbedingung hat.
     
  12. below

    below Kalterer Böhmer

    Dabei seit:
    08.10.06
    Beiträge:
    2.865
    Könnt ihr sowas nicht per mail austragen?

    Alex
     
  13. commander

    commander Baldwins roter Pepping

    Dabei seit:
    25.02.04
    Beiträge:
    3.210
    Nö.

    Les es einfach nicht. Du bist below ;)

    Ich bin und bleibe der festen Überzeugung, dass Rekursion gerade bei mehrdimensionalen Baumoperationen die beweiten einfachere Impelementierung ist - nicht, dass das nicht in einer Schleife zu machen wäre, aber spätestens bei n-dimensionalen Bäumen wirds da mit der Vortsellung manchmal eng - nicht der der Koordinaten, aber übertragen aufs System.

    Bei Verwendung eines rekursivven Aufrufs hat man dagegn nur eine einzige (n-dimensionale) Koordinate, ich find das sehr viel praktischer zu debuggen - und der Verwaltungsoverhead für die n-Stacks entfällt. Dafür hat man natürlich entsprechend mehr Methodenaufrufe.

    Einzig lästig sind die überflüssigen Einstiegparameter solcher rekursiver Methoden und die Ausnahmebehandlung der 0ten Rekursion.

    Abgesehn davon laufen mir solche Methoden bei entsprechendem Einsatzgebiet viel lockerer aus dem Hirn als Schleifen - das mag aber auch Gewohnheit sein.

    Effizienzschwierigkeiten hab ich bei realen Problemen noch nie festgestellt.

    Gruß,

    .commander
     
  14. mullzk

    mullzk Linsenhofener Sämling

    Dabei seit:
    04.01.04
    Beiträge:
    2.529
    noch einmal: ich sage nicht, dass rekursion scheisse sei, ganz im gegenteil. in vielen fällen gibt es eleganteren code (und das ist kein selbstzweck), in nicht wenigen fällen entspricht es mehr der intuitiven herangehensweise (wobei es auch situationen gibt, wo ein iterativer algorithmus der intuition näher kommt) - dementsprechend werden wohl die meisten programmierer regelmässig zu rekursiven ansätzen greifen.

    meine aussage war nur, dass es _kein_ problem gibt, welches nur mit rekursion aber nicht über schleifen berechenbar wäre, dass sie sich in der mächtigkeit irgendwie unterscheiden würden.
    und weil ich schon zuviel zeit in den thread investiert habe, wollte ich noch schnell aufzeigen, dass es situationen gibt, wo rekursion im vergleich zu schleifen unzulänglich ist, und dies eben insb. bei aufgaben ohne definierten haltepunkt, was zum beispiel bei user-interaktion der fall sein kann. denn genau in diesen sachen stösst man mit schleifenlosen sprachen wie haskell (was ja der ausgangspunkt der diskussion war) in mühsame gefilde vor. deshalb habe ich ja im ursprungsthread auch geschrieben, dass ich funktionale sprachen in der web-programmierung (ein aufruf erzeugt eine antwort) als eher überlegen betrachte, während sie sich halt eben für desktop-applikationen (verschiedene inputs erzeugen verschiedene antworten) nur sehr schwerlich und mit grossem murks eignen.
     
  15. MatzeLoCal

    MatzeLoCal Rheinischer Bohnapfel

    Dabei seit:
    05.01.04
    Beiträge:
    2.421
    Wozu gibt es denn Foren?
    Ausserdem zwingt dich niemand in diesem Thread mitzulesen oder ihn gar zu abonnieren. Und ich finde die Diskussion schon interessant.
     
  16. MacMark

    MacMark Biesterfelder Renette

    Dabei seit:
    01.01.05
    Beiträge:
    4.709
    Ich mische mich auch einmal ein :)

    Prinzipiell läßt sich jedes Problem, das man rekursiv lösen kann, auch iterativ lösen.

    Bestimmte Aufgaben sind aber schon von Natur aus rekursiv und lassen sich rekursiv dermaßen elegant lösen, daß man davor in Erfurcht (nicht Erfurt!) niederknien möchte und ein iterativer Ansatz einfach zu umständlich und unangebracht wäre.

    Einfache Beispiele, bei denen sich die rekursive Lösung aufdrängt, wären Fakultät und Fibonacci-Zahlen. Etwas komplexer wären Mandelbrotfraktale (Apfelmännchen) und auch Schach sollte dazugehören.
     
  17. slayercon

    slayercon Meraner

    Dabei seit:
    17.01.05
    Beiträge:
    231
    Bei Operationen auf eine Verzeichnissstruktur (Dateien zählen etc.) mit Unterverzeichnissen ist eine rekursive Funktion auch praktisch ....
     
  18. Senior Sanchez

    Senior Sanchez Damasonrenette

    Dabei seit:
    08.09.06
    Beiträge:
    491
    Ich mag Rekursionen, wirklich ;)

    Aber ich frage mich woher immer die Rekursionsversessenheit bei der Fakultät her kommt. Klar, kann ich das anhand der mathematischen Definition super rekursiv machen, aber ich finde eine iterative um Längen wesentlich einfacher - geht nur mir das so?

    int res;
    for(int i=1; i <= n; i++) {
    res *= i;
    }
     
  19. MacMark

    MacMark Biesterfelder Renette

    Dabei seit:
    01.01.05
    Beiträge:
    4.709
    int fak(int i) {
    if (i==0) return 1;
    else return fak(i-1)*i;
    }
     
  20. Senior Sanchez

    Senior Sanchez Damasonrenette

    Dabei seit:
    08.09.06
    Beiträge:
    491

    Ich weiß wie sie rekursiv aussieht, keine Sorge ;)
    Mir gings nur darum, dass ich die iterative leichter finde, aber standardmäßig die fakultät immer in rekursiver Form gezeigt wird.
     

Diese Seite empfehlen