[HaBo]

Cyber_Puma · 23.04.08, 11:39

Ok danke hab den Unterschied bemerkt.

Trotzdem ist es in dem fall richtig weil die Aufgabenstellung es hier so verlangt, aber ich hab kapiert was du meinst.

LG

**CDW** · 23.04.08, 18:31

Zitat:

programmiere nur mal z.b. die fibonacci-zahlen rekursiv und iterativ, dann siehst du ganz schnell den unterschied

Immer dieses Rekursionbashing

. Es gibt genug Algorithmen, die entweder gar nicht (dabei wird der Stack "mit in die Prozedur" genommen oder anders simuliert) oder nur mit viel Mühe auf iterativ umgeschrieben werden können - Parsing, Baumoperationen (Balansierung, Suche(?) ) Backtracking usw. Ist leider schon ein Jährchen her, so dass ich nicht mehr die Beispiele im Kopf habe - das Problem ist nur, dass Rekursion "ganz doof" beigebracht wird (sinnloser Einsatz wie z.B die naive Fibonacci Berechnung) und daher immer etwas negatives daran haftet.

Bps Fibonacci: nur weil die mathematische Definition rekursiv ist, muss man die ja nicht 1:1 übernehmen. Denn

Code:

public static long fib(int a){
  if (a==1||a==2) return 1;
  else return fib(a-1)+fib(a-2);
}

wird 2^a mal aufgerufen (ok, besser gesagt, Fibonacci Wachstum ist expoteniell und lässt sich glaube ich für größere Sachen recht gut mit n^k vorhersagen, hab jetzt aber keine Lust danach zu suchen

). Bei der iterativen Umsetzung hat man aber einen komplett anderen Ansatz - man beginnt am Anfang der Folge und geht immer Zahl um Zahl durch - wohl weil die andere Methode iterativ schwer umsetzbar wäre

)
Man vergleicht also Äpfel mit Birnen um dann festzustellen, dass Rekursion schlecht ist.

jedenfalls, Fibonacci rekursiv:

Code:

static  long fib(int a, long aktuell, long vorher)
	{   
	   long temp=aktuell;
	   aktuell=aktuell+vorher;
	   vorher=temp;
	   if (a>3) return fib(a-1, aktuell, vorher);
	   return aktuell+vorher;
	}

(Sonderfall für die erste Fibonaccizahl wurde nicht berücksichtigt

)
definiert man vorher/aktuell so:

Code:

{
long aktuell=0; long vorher=1;

static  long fib(int a)
	{   
	   long temp=aktuell;
	   aktuell=aktuell+vorher;
	   vorher=temp;
	   if (a>3) return fib(a-1);
	   return aktuell+vorher;
	}
}

ist vielleicht nicht so ganz elegant, der Overhead gegenüber der iterativer Umsetzung ist aber minimal

**Elderan** · 23.04.08, 19:29

Hallo,
Die iterative Lösung der Fib.-Zahlen ist schon besser. Möchte man große Fibonacci Zahlen rekursiv berechnen, selbst mit einer verbesserten rekursiven Formeln, kann dies zu erheblichen Problemen führen. Vermutlich erhält man dann irgendwann die Meldung, dass der Stack voll sei (+Programm bricht), da bei jedem Funktionsaufruf die entsprechenden Zeiger auf den Stack gelegt werden müssen.

Verwendet man stattdessen eine normale Schleife, lassen sich eigentlich problemlos beliebig große Fibonacci-Zahlen berechnen, ohne gefahr zu laufen, dass einem der Stack explodiert.

Auch wenn der Speicher/Stack u.ä. vernachlässigt werden könnte, wäre die iterative Variante schneller.
Bei der rekursive Funktion habe ich min. zwei Sprünge, einmal in die Funktion und einmal wieder heraus.
Bei der iterativen Formel habe ich aber pro Durchlauf nur einen Sprung + 1 Sprung für die Abbruchbedingung.
D.h., rekursiv muss ich doppelt so oft springen wie bei der iterativen Variante, und Sprünge verbrauchen extrem viel Zeit.

Aber ansonsten stimmt es, viele Algorithmen lassen sich extrem schön rekursiv lösen (z.B. alle Dateien in einem Ordner inkl. Unterordner auflisten (also Bäume durchlaufen)) und die iterative Variante macht bei diesen kaum/keinen Sinn und wirkt nur unheimlich aufbeläht. Kommt immer drauf an.

Zitat:

das Problem ist nur, dass Rekursion "ganz doof" beigebracht wird (sinnloser Einsatz wie z.B die naive Fibonacci Berechnung) und daher immer etwas negatives daran haftet.

Oder das Standardbeispiel Fakultät berechnen: n!

Code:

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

Da fragt man sich auch, warum man sowas nicht per Schleife macht.

**CDW** · 23.04.08, 19:52

Mir ist beim Essen eine viel schönere rekursive Fibonacciform eingefallen

:

Zitat:

static long fib(int a, long aktuell, long vorher)
{
if (a>2) return fib(a-1, aktuell+vorher, aktuell);
return aktuell+vorher;
}

aufruf: fib(10,0,1);

Ansonsten - meistens geht es doch darum, den Code lesbar zu lassen und nicht die letzen ns rauskitzeln und dafür irgendwelche Fehler in der Umsetzun zu übersehen

z.B hier bei Fibonacci: bevor der Stack abraucht, bekommt man schon zig mal einen Überlauf von long&Co - ist also immer eine Abwägungssache.

BTW: ich muss gerade an eine Mathestudentin denken, die in ihrem Zulassungsprojekt (DBS), um an das vorletze Datum mit einem zugehörigen Eintrag zu kommen sich rekursiv durch die ganze Tabelle gehangelt hat (die SQL Anfrage+bisschen Javacode sahen dafür ganz elegant aus

) - und den armen, schwächlichen (und wohl etwas mies konfigurierten) DB2 "Versuchsserver" ganz alleine blockierte. Ärgerlich für alle, die ihre Projekte vor der Abgabe noch testen wollten

nuki · 21.06.11, 21:14

Hey leute
kann mir jemand sagen wie ich das auf C programmieren kann?? :-S
ich verzweifle schon seit über ner Woche... ich komm einfach nicht weiter...

Eydeet · 22.06.11, 12:34

OT:
Zu dem Rekursions-Ding möchte ich auch noch etwas beitragen.
Wenn man die Fibonacci-Folge wie CDW implementiert, dann können moderne Compiler die Rekursion wegoptimieren (-> Tail Recursion). Damit sollte sich auch das Problem mit überlaufenden Stacks erledigt haben.
Ich habe mal ein kleines Testprogramm geschrieben, das CDWs Implementation mit dieser iterativen vergleicht:

Code:

long fibi(long a)
{
    long fib0 = 0, fib1 = 1, fib2, i;
    for (i = 2; i < a; i++) {
        fib2 = fib0 + fib1;
        fib0 = fib1;
        fib1 = fib2;
    }
    return fib2;
}

Die Ergebnisse sind folgende, für die Berechnung von 10000 Fibonacci-Zahlen (1..9999) (GCC 4.2.1):

Code:

O0:
rek clocks: 422393
itr clocks: 223544

O2:
rek clocks: 50335
itr clocks: 51078

Os:
rek clocks: 24751
itr clocks: 57327

rek ist das rekursive, itr, das iterative Programm.

Damit wird deutlich, dass der Compiler rekursive Programme in zumindest machen Fällen besser optimieren kann als iterative. Eine Verteufelung dieser ist damit meiner Meinung nach nicht gerechtfertigt.

Die schnellste Implementation sollte übrigens diese sein:

Code:

long fib(long a)
{
    const double phi = 1.6180339887498949;
    const double sq5 = 2.2360679774997898;
    return (long)(0.5 + pow(phi, a) / sq5);
}

// Edit
B2T:

Auch die beiden (bisher ähnlich schon aufgetauchten) Hanoi-Varianten, rekursiv und iterativ, möchte ich noch einmal gegeneinander stellen.

Code:

long dummy = 0, dummy2 = 0;

void hanoi_r(a, b, c, h)
{
    if (h > 1) {
        hanoi_r(a, c, b, h-1);
        hanoi_r(a, b, c, 1);
        hanoi_r(b, a, c, h-1);
    } else {
        dummy += a - c;
        //printf("Lege Scheibe von %d nach %d\n", a, c);
    }
}

void hanoi_i(h)
{
    int x;
    for (x = 1; x < (1 << h); x++) {
        int a = (x & x-1) % 3;
        int c = ((x | x - 1) + 1) % 3;
        dummy2 += a - c;
        //printf("Lege Scheibe von %d nach %d\n", a, c);
    }
}

Die Dummy-Counter haben nur den Zweck, dass der Compiler mir die Schleifen nicht komplett wegoptimiert. Die Ausgabe ist natürlich auskommentiert, da hier der größte Teil der Rechenzeit verbraucht wird.
Eine Performance-Messung für eine Höhe von 28 ergibt bei mir folgende Ergebnisse:

Code:

unoptimiert (GCC 4.2.1):
hanoi_r clocks: 3243513
hanoi_i clocks: 3290201

O3-optimiert (GCC 4.2.1):
hanoi_r clocks: 1358059
hanoi_i clocks: 1584307

O3-optimiert (LLVM-GCC 4.2):
hanoi_r clocks: 1085470
hanoi_i clocks: 1908822

Dass auch hier die rekursive Variante wieder besser abschneidet wundert auch mich, aber es zeigt, dass Rekursion, wie CDW schon gesagt hat, einen viel zu schlechten Ruf hat. Ich vermute mal, dass sich die rekursive Version besser optimieren lässt, da rekursiv aufgeschriebene Algorithmen oft mathematisch besser handhabbar sind.

Anzeige

- Anzeige -

23.04.08, 11:39	#16 (permalink)
Cyber_Puma Registriert seit: 14.11.07 Likes: 0	Anzeige Ok danke hab den Unterschied bemerkt. Trotzdem ist es in dem fall richtig weil die Aufgabenstellung es hier so verlangt, aber ich hab kapiert was du meinst. LG

22.06.11, 12:34	#21 (permalink)
Eydeet Registriert seit: 14.04.06 Likes: 4	OT: Zu dem Rekursions-Ding möchte ich auch noch etwas beitragen. Wenn man die Fibonacci-Folge wie CDW implementiert, dann können moderne Compiler die Rekursion wegoptimieren (-> Tail Recursion). Damit sollte sich auch das Problem mit überlaufenden Stacks erledigt haben. Ich habe mal ein kleines Testprogramm geschrieben, das CDWs Implementation mit dieser iterativen vergleicht: Code: long fibi(long a) { long fib0 = 0, fib1 = 1, fib2, i; for (i = 2; i < a; i++) { fib2 = fib0 + fib1; fib0 = fib1; fib1 = fib2; } return fib2; } Die Ergebnisse sind folgende, für die Berechnung von 10000 Fibonacci-Zahlen (1..9999) (GCC 4.2.1): Code: O0: rek clocks: 422393 itr clocks: 223544 O2: rek clocks: 50335 itr clocks: 51078 Os: rek clocks: 24751 itr clocks: 57327 rek ist das rekursive, itr, das iterative Programm. Damit wird deutlich, dass der Compiler rekursive Programme in zumindest machen Fällen besser optimieren kann als iterative. Eine Verteufelung dieser ist damit meiner Meinung nach nicht gerechtfertigt. Die schnellste Implementation sollte übrigens diese sein: Code: long fib(long a) { const double phi = 1.6180339887498949; const double sq5 = 2.2360679774997898; return (long)(0.5 + pow(phi, a) / sq5); } // Edit B2T: Auch die beiden (bisher ähnlich schon aufgetauchten) Hanoi-Varianten, rekursiv und iterativ, möchte ich noch einmal gegeneinander stellen. Code: long dummy = 0, dummy2 = 0; void hanoi_r(a, b, c, h) { if (h > 1) { hanoi_r(a, c, b, h-1); hanoi_r(a, b, c, 1); hanoi_r(b, a, c, h-1); } else { dummy += a - c; //printf("Lege Scheibe von %d nach %d\n", a, c); } } void hanoi_i(h) { int x; for (x = 1; x < (1 << h); x++) { int a = (x & x-1) % 3; int c = ((x \| x - 1) + 1) % 3; dummy2 += a - c; //printf("Lege Scheibe von %d nach %d\n", a, c); } } Die Dummy-Counter haben nur den Zweck, dass der Compiler mir die Schleifen nicht komplett wegoptimiert. Die Ausgabe ist natürlich auskommentiert, da hier der größte Teil der Rechenzeit verbraucht wird. Eine Performance-Messung für eine Höhe von 28 ergibt bei mir folgende Ergebnisse: Code: unoptimiert (GCC 4.2.1): hanoi_r clocks: 3243513 hanoi_i clocks: 3290201 O3-optimiert (GCC 4.2.1): hanoi_r clocks: 1358059 hanoi_i clocks: 1584307 O3-optimiert (LLVM-GCC 4.2): hanoi_r clocks: 1085470 hanoi_i clocks: 1908822 Dass auch hier die rekursive Variante wieder besser abschneidet wundert auch mich, aber es zeigt, dass Rekursion, wie CDW schon gesagt hat, einen viel zu schlechten Ruf hat. Ich vermute mal, dass sich die rekursive Version besser optimieren lässt, da rekursiv aufgeschriebene Algorithmen oft mathematisch besser handhabbar sind. Geändert von Eydeet (22.06.11 um 15:45 Uhr)

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Ansicht
Linear-Darstellung Zur Hybrid-Darstellung wechseln Zur Baum-Darstellung wechseln

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
Türme von Hanoi (grafisch) in Java	Olli Kern	Code Kitchen	2	24.06.04 12:42

21.06.11, 21:14	#20 (permalink)
nuki Registriert seit: 21.06.11 Likes: 0	Hey leute kann mir jemand sagen wie ich das auf C programmieren kann?? :-S ich verzweifle schon seit über ner Woche... ich komm einfach nicht weiter...

[HaBo]

Türme von Hanoi