Rekursion vs. Schleife

[Skeeve]

Hier der Urspungsthread...

dass wir einen ernstgemeinten Haskell-Frage-Thread nicht weiter mit protzigem Ich-Habe-Recht-Macho-Gehabe belasten

Den Stiefel ziehst aber bitte Du Dir an.

Man kann doch z.B. einfach einen Stack nachbilden

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.

Yup, das mit der Beweislast ist klar - such du mir eine Rekursion, von der du glaubst, dass man sie unmöglich mit einer Iteration machen kann

Kein Problem:

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 ) )
}

 

[mullzk]

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.

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.

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:

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)

 

[Skeeve]

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?

 

[mullzk]

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...

 

[Skeeve]

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.

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.

 

[newman]

Allerdings (und das meint "rekursionsimmanent") liegt einer Rekursion immer ein Stack (in welcher Implementierung auch immer) zugrunde.

*unterschreib*

 

[.holger]

oki eki

 

[mullzk]

ok, alles klar, streitigkeit beendet. wieder freunde?

 

[Skeeve]

Wieder freunde?

Ich habe Dich nie als Feind betrachtet.

 

[mullzk]

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!
alles gute aus dem kalten bern
mullzk

 

[Skeeve]

hier noch die erläuterung meiner aussage im haskell-thread, dass rekursionen _in der praxis_ zT weniger mächtig sind: endlos laufende programme

Meiner Meinung nach ist das keine sinnvolle rekursive Funktion, da sie keine erreichbare Abbruchbedingung hat.

 

[below]

Könnt ihr sowas nicht per mail austragen?

Alex

 

[commander]

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

 

[mullzk]

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.

 

[MatzeLoCal]

Könnt ihr sowas nicht per mail austragen?

Alex

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.

 

[MacMark]

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.

 

[slayercon]

Bei Operationen auf eine Verzeichnissstruktur (Dateien zählen etc.) mit Unterverzeichnissen ist eine rekursive Funktion auch praktisch ....

 

[Senior Sanchez]

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.

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;
}

 

[MacMark]

int fak(int i) {
if (i==0) return 1;
else return fak(i-1)*i;
}

 

[Senior Sanchez]

int fak(int i) {
if (i==0) return 1;
else return fak(i-1)*i;
}

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.