Rekursion vs. Schleife

[MacMark]

Dein iterativer Ansatz benötigt 3 Variablen im Quelltext, der rekursive nur 1. Das zeigt doch schon wie 1-fach es ist.

 

[saarmac]

Ich will mich ja nicht beklagen, aber schleifen basieren auf Rekursion sind nur für den Anwender übersichtlicher.
Was im Endeffekt schneller ist hängt von der jeweiligen Programmiersprache ab. C++ ist in rekursion zum Beispiel ziemlich scheiße im Vergleich zu standard ML. Dafür stark bei Schleifen.

Für den den es Wirklich Interessiert hier was zum Nachlesen

http://www.ps.uni-sb.de/~smolka/Programmierung/2006-11-07.pdf
(enthält auch interessantes über Laufzeit und so. sollte man vielleicht mal gelesen haben das ding, wird auch erklärt wie innterpreter funktioniere som mit lexer, parser, wie die semantiken aufgebaut sind und so. Echt eine Grundlage für jeden wissenschaftlich orientierten Informatiker. Für Code Tipper aber eher uninteressant)

viel Spaß

 

[saarmac]

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

In diesem Beispiel ist die Rekursion zum Beispiel schlecht da sie nicht endrekursiv implementiert ist. Mit einem Akku is das gleich viel besser!

 

[Skeeve]

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

Nur, wenn Du Stacks zuläßt. Siehe oben. Eine Rekursion basiert immer auf einem Stack. In diesem Fall (Ackermannfunktion) wird mit dem Stack die Rekursion nachgebildet. Somit ist, nach meinem Dafürhalten immer noch rekursiv gelöst.

 

[Trapper]

Nur, wenn Du Stacks zuläßt.

Ein Stack ist eine normale Datenstruktur, wie es noch eine Vielzahl andere gibt - warum sollte man diese auch verbieten?

Eine Rekursion basiert immer auf einem Stack.

Und eine Schleife immer auf einer Schleifenvariable. Ist demnach bei einer Rekursion kein Variablenzugriff erlaubt, weil Schleifen darauf basieren?

In diesem Fall (Ackermannfunktion) wird mit dem Stack die Rekursion nachgebildet. Somit ist, nach meinem Dafürhalten immer noch rekursiv gelöst.

Dann hast du eine falsche Definition von Rekursion. Die Essenz einer rekursiven Funktion (man beachte! Es muss sich um eine Funktion handeln - das hat mit dem obigen Schleifenkonstrukt schonmal gar nix zu tun) ist, dass sie sich selbst aufruft.

 

[Skeeve]

Ein Stack ist eine normale Datenstruktur, wie es noch eine Vielzahl andere gibt - warum sollte man diese auch verbieten?

Das hatten wir alles schon. Nur weil die Funktion sich nicht explizit selbst aufruft, wird daraus immer noch keine iterative Funktion.

Im Gegensatz zu Fakultät, die Du sowohl rekusiv ( f(1)=1 ; f(n)=n*f(n-1) ), als auch iterativ ( f(n)= Prod[i=1..n](i) ) definieren kannst, wird Dir eine rein iterative Definition der Ackermann Funktion nicht gelingen.

Bevor Du Dich weiter darüber ausläßt, versuch doch bitte zunächst mal den Begriff der primitive Rekursivität zu verstehen.

 

[MacMark]

In diesem Beispiel ist die Rekursion zum Beispiel schlecht da sie nicht endrekursiv implementiert ist. Mit einem Akku is das gleich viel besser!

Du siehst die Abbruchbedingung (i==0) nicht?

 

[MacMark]

Nur, wenn Du Stacks zuläßt. Siehe oben. Eine Rekursion basiert immer auf einem Stack. In diesem Fall (Ackermannfunktion) wird mit dem Stack die Rekursion nachgebildet. Somit ist, nach meinem Dafürhalten immer noch rekursiv gelöst.

Wie im Beispiel mit der Fakultät zu sehen ist, wird da kein Stack verwendet und auch keine Rekursion nachgebildet.

 

[mullzk]

hüstel, ähh, jetzt melde ich mich halt doch wieder in diesem thread

Das hatten wir alles schon. Nur weil die Funktion sich nicht explizit selbst aufruft, wird daraus immer noch keine iterative Funktion.

sorry, aber was willst du damit sagen. dass die funktion - obwohl sie sich nicht explizit und auch nicht implizit selbst aufruft - eine rekursive funktion sein soll?

Im Gegensatz zu Fakultät, die Du sowohl rekusiv ( f(1)=1 ; f(n)=n*f(n-1) ), als auch iterativ ( f(n)= Prod[i=1..n](i) ) definieren kannst, wird Dir eine rein iterative Definition der Ackermann Funktion nicht gelingen.

hust. ähh, was war denn das, was ich oben gemacht habe? eine iterative variante von ackermann oder nicht? und dann, weil du bei deinem standpunkt von stack unvereinbar mit iterativ bliebst, eine iterative variante von stack oder nicht? irgendwo ein fünkchen rekursion?

Bevor Du Dich weiter darüber ausläßt, versuch doch bitte zunächst mal den Begriff der primitive Rekursivität zu verstehen.

ok, dann erklär du uns mal deine begrifflichkeit - mir scheint nicht, dass einer von uns das ganze nicht begriffen hat, sondern dass wir uns auf grundlegend unterschiedliche begriffe bezüglich primitive rekursion, µ-Rekursion und Iteration stützen.
Für meine Verwendung der Begrifflichkeit stütze ich mich auf die Konzepte, wie sie von Uwe Schöning 1992 dargestellt werden, und meines Wissens seit Turing und Church ziemlich oft verwendet werden, im Informatik-Duden stehen und auch in der Wikipedia verbreitet sind.

wenn du sagst, dass sprachen ohne stack weniger mächtig sind als solche mit, helfe ich mit, auch wenn ich noch nie von einer sprache ohne stack gehört hätte. aber solange du rekursion gegen iteration (entsprechend meiner - und wie ich meine kanonischen - begrifflichkeit) auf der ebene der berechenbarkeit gegeneinander ausspielen wirst, widerspreche ich vehement. selbstverständlich darfst du versuchen, die curch'sche these zu wiederlegen, turing-preis wäre dir dabei sicher, aber offen gesagt zweifle ich daran, dass dies jemals jemand hinbringen wird...

 

[mullzk]

Du siehst die Abbruchbedingung (i==0) nicht?

ähh, endrekursion hat nichts mit abbruch-bedingung zu tun. endrekursion bedeutet, dass jeder rekursionsschritt in sich abgeschlossen ist und nicht auf ergebnisse tieferer rekursionsebenen warten muss - so dass man bei grösseren berechnungen nicht einen cray nur für den stack einschalten muss.
endrekursion macht man meist mittels akkumulatoren, also dass man das ergebnis der aktuellen rekursionsstufe der nächsten mitgibt.

 

[MacMark]

Mag sein. Mir ging es darum, den iterativen Ansatz in Punkto Einfachheit zu schlagen.

 

[mullzk]

Mag sein. Mir ging es darum, den iterativen Ansatz in Punkto Einfachheit zu schlagen.

full ack - wie ich oben mal gepostet habe: rekursive ansätze sind meist eleganter und oft intuitiver als iterative ansätze. mit endrekursion sind sie oft nicht mal weniger effizient als iteration

aber sie sind nie nie nie mächtiger als iteration, verdammt nochmal:-D

so, und jetzt mach ich schluss mit theoretischer info für heute

 

[saarmac]

Du siehst die Abbruchbedingung (i==0) nicht?

Doch schon aber das hat nichts mit Endrekursion zu tun.

"Unter einer endrekursiven Prozedur versteht man eine linear-rekursive Prozedur,
bei der das Ergebnis bei jedem Rekursionsschritt direkt durch die rekursive
Anwendung der Prozedur geliefert wird. Ein typisches Beispiel ist die Prozedur
gcd aus Abbildung 9.1"

Bei deiner Prozedur muss immer noch das i multipliziert werden.

Aber ich halte mich jetzt mal aus der Diskussion raus und lache lieber noch ein bisschen.

 

[Skeeve]

hust. ähh, was war denn das, was ich oben gemacht habe? eine iterative variante von ackermann oder nicht?

Sie ist rekursiv, auch wenn sie nicht so aussieht. Alleine dadurch, wie Du den Stack verrwendest:

INPUT (x,y);
INIT (stack);
PUSH (x, stack);
PUSH (y, stack);
WHILE size(stack) != 0 DO { # Müßte das nicht 1 sein?
	y:= POP(stack);
	x:= POP(stack); # Hier holst Du die Argumente für a vom Stack
	IF x=0 {
		THEN PUSH(y+1, stack); # Hier schiebst Du das Ergebnis auf den Stack
	} ELSEIF y=0 {
		THEN PUSH(x-1, stack); # Hier schiebst Du die veränderten
		PUSH(1,stack); # Ausgangswerte wieder auf den Satck
		# Im Prinzip ließe sich bis hierher alles ohne Rekursion und
		# somit auch ohne Stack lösen
	} ELSE {
		PUSH(x-1, stack); # Hier schiebst Du einen Parameter auf den Stack
		# der erst sehr viel später wieder verwebdet wird.
		# Dies ist vom Prinzip her eine Rückkehradresse
		PUSH(x, stack); # Hier kommen 2 Werte auf den Stack
		PUSH(y-1, stack); # Dieser Teil ginge auch noch ohne Rekursion
		# Durch den einen zusätzlichen Wert ersetzt Du den explizite
		# rekursiven Aufruf.
	}
}
result := POP(stack)
OUTPUT(result)

Alleine dadurch, daß Du den expliziten rekursiven Aufruf kaschierst, wird es nicht nicht-rekursiv. Vergleiche auch http://www.mathematik.uni-ulm.de/sai/ss99/prog/skript/rekursion-07.html

 

[Senior Sanchez]

Ich kenne als Definition der Rekursion, dass damit Funktionen oder Datenstrukturen gemeint sind, die teilweise oder vollständig durch sich selbst definiert sind.

Was jetzt allerdings den Umbau einer rekursiven Funktion zu einer iterativen unter Zuhilfenahme eines Stacks betrifft, so erkenne ich in der iterativen Variante keine Rekursion, auch wenn vielleicht irgendwelche Ähnlichkeiten da sein können.

 

[Skeeve]

Was jetzt allerdings den Umbau einer rekursiven Funktion zu einer iterativen unter Zuhilfenahme eines Stacks betrifft, so erkenne ich in der iterativen Variante keine Rekursion, auch wenn vielleicht irgendwelche Ähnlichkeiten da sein können.

Naja... Dann schaust Du vielleicht nicht richtig hin.

 

[Senior Sanchez]

Kann sein.

Aber vielleicht fasse ich auch irgendwelche Dinge, die irgendwie mit Merkmalen der Rekursion zu tun haben könnten, nicht gleich als rekursion-kaschierend auf.

Aus deiner Darstellung könnte man fast schlussfolgern, dass immer wenn ein Stack zum Einsatz kommt, es sich um Rekursion handelt und dem möchte ich doch widersprechen.

 

[Skeeve]

Aus deiner Darstellung könnte man fast schlussfolgern, dass immer wenn ein Stack zum Einsatz kommt, es sich um Rekursion handelt und dem möchte ich doch widersprechen.

Dem würde ich auch widersprechen.

In diesem Fall ist es so, daß eine Schleife immer wieder läuft, aber mit Hilfe eines Stacks Zwischenstände speichert um später an der Stelle weiterarbeiten zu können.

Dies ist exakt das, was die rekursive Variante der Ackermann Funktion auch macht. Nur macht sie es dadurch, daß die Funltion explizit aufgerufen wird und damit der Stack, der jeder Rekursion ja zugrunde liegt, genutzt wird.

Es wird hier also nur die Rekursion, wie es im verlinkten Artikel heißt, "von Hand nachprogrammiert".

 

[Senior Sanchez]

Hmm, aber nur weil man die Rekursion "von Hand nachprogrammiert" ist es meiner Ansicht noch lange keine rekursive Lösung.

In diesem Fall ist es so, daß eine Schleife immer wieder läuft, aber mit Hilfe eines Stacks Zwischenstände speichert um später an der Stelle weiterarbeiten zu können.

Das ist bei dynamischem Programmieren genauso, trotzdem haste da nicht immer eine Rekursion vorliegen.

Ich verstehe schon was du meinst, aber ich würde nicht soweit gehen und behaupten, dass es sich immernoch um eine Rekursion handelt.

 

[Skeeve]

Ich verstehe schon was du meinst, aber ich würde nicht soweit gehen und behaupten, dass es sich immernoch um eine Rekursion handelt.

Das Problem ist einfach, daß es für die Ackermann Funktion nun mal keine Nicht-rekursive Definition gibt. Und mit "Definition" meine ich hier die mathematische Bedeutung. Nicht etwa irgendwelche Repräsentationen als Programm. Ackermann ist nun mal so definiert, daß ein Ergebnis auf anderen Ergebnissen aufgebaut ist.

Bei Fakultät gibt es zum einen die rekursive Definition:
Die Fakultät von 1 ist 1,
Die Fakultät von n ist das Produt aus n und der Fakultät von n-1

Oder die iterative
Die Fakultät von n ist das Produkt der natürlichen Zahlen von 1 bis n

Eine iterative Definition dieser Art kann für Ackermann nicht aufgestellt werden.