Rekursion vs. Schleife

[milamber]

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.

eben!
Programmieren ist wie Gedichte schreiben, und sowas ist einfach schön:

public static int ggt(int x, int y) {
if (y==0) return x;
else return ggt(y,x%y);
}

 

[Skeeve]

eben!
Programmieren ist wie Gedichte schreiben, und sowas ist einfach schön:

Dann solltest Du Dir mal die Perl Poetry ansehen.

Zum Beispiel dies hier:

connect $me, $you; sin;
local $anesthetic while $painful;
push @{'%#@^@$!'} until pop @kid;
chop my $umbilical_cord;
bless our $family

 

[Senior Sanchez]

Na das macht die Sache doch klarer, jetzt versteh ich besser was du meinst.
Ja, das ist in der Tat so, wenngleich man aber eben in der Programmrepräsentation unter zuhilfenahme eines Stacks eine iterative Lösung hinbekommen kann.

 

[Skeeve]

wenngleich man aber eben in der Programmrepräsentation unter zuhilfenahme eines Stacks eine iterative Lösung hinbekommen kann.

Nur: Was hat man davon? Dadurch wird es auch nicht besser oder schneller berechenbar. Das Schöne an wirklich iterativen Implementierungen ist ja gerade, daß sie keinen Stack benötigen und somit nicht maßlos Platz anfordern müssen. Zumindest ist es das, was ich mit "iterativ" verbinde.

 

[Senior Sanchez]

Naja, Beispiel von Java:
Die JVM hat ne interne Stacksize die indirekt die Anzahl der Methodenaufrufe und somit auch die Rekursionstiefe begrenzt. Klassische Stacks die dagegen auf dem Heap liegen können somit wesentlich größer werden, da die Heapsize größer ist als die Stacksize.

 

[tjp]

Nur: Was hat man davon?

Die Stackgröße ist immer stark eingeschränkt. Die MacOS X Vorgabe scheint 8MB zu sein. Auch nicht wirklich viel.