Rekursion vermeiden... Wieso?

volkard

zwutz schrieb:

volkard schrieb:

Warum ist mein Stack auf 1M beschränkt, obwohl ich 2G Speicher zur Verfügung habe? Warum stelle ich das nicht um auf 2G Stackspeicher?

würde das nicht bedeuten, dass jeder Thread 2GB bekommt? Die werden sich ja kaum einen Stack teilen

Ja, das wäre nett. Jeder Prozess hat ja auch 2G Heap.

knivil

Warum ist mein Stack auf 1M beschränkt, obwohl ich 2G Speicher zur Verfügung habe? Warum stelle ich das nicht um auf 2G Stackspeicher?

Also, mal abgesehen vom Unnutzen ist es so, dass ... aber vielleicht sollte ich keine rhetorischen Fragen beantworten ...

volkard schrieb:

Weiß auch jemand, WARUM der Stackspeicher so beschränkt ist? Normalerweise in C und C++ nur 1MB. Vielleicht sollte man darüber nachdenken, wie man diese beschränkung loswerden kann

die 1MB sind ja nur 'ne default-einstellung. unter windoof kannste z.b. 'CreateThread' sagen, wieviel stackspeicher du brauchst. also auch 1000 MB oder 5 bytes, wenn's sein muss.
schau hier: http://msdn.microsoft.com/en-us/library/ms686774(VS.85).aspx

volkard

;fricky schrieb:

volkard schrieb:

Weiß auch jemand, WARUM der Stackspeicher so beschränkt ist? Normalerweise in C und C++ nur 1MB. Vielleicht sollte man darüber nachdenken, wie man diese beschränkung loswerden kann

die 1MB sind ja nur 'ne default-einstellung. unter windows kannste z.b. 'CreateThread' sagen, wieviel stackspeicher du brauchst. also auch 1000 MB oder 5 bytes, wenn's sein muss.
schau hier: http://msdn.microsoft.com/en-us/library/ms686774(VS.85).aspx

Hab ich natürlich alles schon benutzt. Die Frage ist, warum tut man so gerne 1M nehmen statt 2G? Falls jemand meint, daß 2G nicht ginge, warum?

volkard schrieb:

Die Frage ist, warum tut man so gerne 1M nehmen statt 2G? Falls jemand meint, daß 2G nicht ginge, warum?

1MB sind wahrscheinlich ein guter kompromiss. wenn jeder thread schon beim start 2GB virtual memory für nix reservieren würde, wären weniger pages für andere dinge verfügbar.

FlashBurn

Ich habe den Thread nur mal kurz überflogen und wollte mal ein Bsp bringen.

Nehmt den AVL-Baum, den kann man rekursiv und iterativ implementieren. So ich behaupte jetzt das die rekursive Variante ab einer bestimmten Baumgröße weniger Speicher (Stack + Baum) verbraucht als die iterative (Stack + Baum). Denn will man den AVL Baum iterativ implementieren muss man parent Pointer nutzen (da man die "Probleme" ja auf dem Rückweg behebt). Klar ist die iterative schneller (keine ständigen Funktionsaufrufe) und auch ist hier tail-rekursion nicht möglich, da man ja beim zurück springen weiter arbeitet.

So und nun mal dazu was ich unter Rekursion verstehe und was unter Iteration.

Rekursion:

struct node_t *find(struct node_t *node, int val) {
  if(node == 0)
    return 0;

  if(node->val == val)
    return node;

  if(node->val - val > 0)
    return find(node->left,val);
  else
    return find(node->right,val);
}

Und jetzt iterativ:

struct node_t *find(struct node_t *node, int val) {
  while(node) {
    if(node->val == val)
      return node;
    if(node->val - val > 0)
      node= node->left;
    else
      node= node->right;
  }

  return 0;
}

Das wäre auch ein Bsp wo tail-rekursion gehen würde, sollte auch nur ein Bsp sein. Hier wäre die iterative Variante schneller und verbraucht weniger Speicher. Ist halt nur nicht immer so.

volkard

FlashBurn schrieb:

Nehmt den AVL-Baum, den kann man rekursiv und iterativ implementieren. So ich behaupte jetzt das die rekursive Variante ab einer bestimmten Baumgröße weniger Speicher (Stack + Baum) verbraucht als die iterative (Stack + Baum). Denn will man den AVL Baum iterativ implementieren muss man parent Pointer nutzen (da man die "Probleme" ja auf dem Rückweg behebt).

Du vergleichst Äpfel mit Birnen.
Nun ist die maximale Tiefe ja bekannt. Sagen wir mal 40. Nehmen tun Array der Größe 40 und ich kann die History genausogut speichern.

FlashBurn

Wieso ist die maximale Tiefe bekannt?

Wie wäre es denn wenn Jemand mal ein Bsp bringen würde, wo eine Rekursion vermieden werden sollte, zwecks Stackoverflow!?

volkard

FlashBurn schrieb:

Wie wäre es denn wenn Jemand mal ein Bsp bringen würde, wo eine Rekursion vermieden werden sollte, zwecks Stackoverflow!?

Sortiertes Einfügen in eine verkettete Liste.

FlashBurn schrieb:

Wieso ist die maximale Tiefe bekannt?

Weil der Baum ballanciert ist und ein Knoten mindestens zwei Zeiger drin hat Byte hat und nur
a) 64K Speicher adressierbar sind, macht max 16384 Knoten macht maxTiefe < 20
b) 4G Speicher adressierbar sind, macht max 536870912 Knoten macht maxTiefe < 42
c) 16EB Speicher adressierbar sind, macht max 1152921504606846976 Knoten macht maxTiefe < 87

FlashBurn

Das mit der Tiefe ist mir dann auch noch aufgefallen.

Ok, wer kommt aber auf die Idee ein sortiertes Einfügen in eine verkettete Liste rekursiv zu machen? Vorallem, was bringt das?

Ich würde Rekursion nur da anwenden wo es von der Datenstruktur her Sinn macht und eine Liste iteriert man nun mal.

volkard

FlashBurn schrieb:

Ok, wer kommt aber auf die Idee ein sortiertes Einfügen in eine verkettete Liste rekursiv zu machen?

Professoren und Lehrbuchautoren.

FlashBurn schrieb:

Vorallem, was bringt das?

Es bringt mir viel Arbeit, weil ich den N00bs dann wieder ausreden darf, jeden Furz rekursiv zu erzeugen.

FlashBurn

Das ist lustig, alle Professoren die ich bisher hatten, tun sich sogar schwer damit nen Baum rekursiv zu bearbeiten, da ärgern sie lieber die Studenten und machen das ganze iterativ

Also wie gesagt, Rekursion nur da wo es auch Sinn macht (vorallem wenn es den Code vereinfacht), aber iterativ ist eigentlich (weil mir es bestimmt auch Bsp gibt wo es nicht so ist) immer schneller, aber leider oft auch komplexer.

frosch03

Na, das sind jetzt doch sehr persönliche Beweggründe. (Und ich will jetzt garnicht
sagen, dass ich das nicht verstehen und/oder nachvollziehen kann)

Allerdings bin ich der Meinung, dass man einer sehr allgemein gehaltenen
Fragestellung nicht nicht mit so spezielle Antworten entgegentreten sollte.

Listen und Bäume sind nun mal Datenstrukturen, die es auch außerhalb des
imperativen Programmier-Paradigmas gibt. Und daher ist es falsch zu sagen, man
sollte diesen generell nicht mit Rekursion begegnen.

Und um nochmal mit der avl-baum-tiefe zu sticheln :xmas1:
Niemand hat behauptet, dass der Tree die ganze Zeit im RAM liegen muss *duck*

Naja, nichts für ungut ne
frosch03

hustbaer

FlashBurn schrieb:

Also wie gesagt, Rekursion nur da wo es auch Sinn macht (vorallem wenn es den Code vereinfacht), aber iterativ ist eigentlich (weil mir es bestimmt auch Bsp gibt wo es nicht so ist) immer schneller, aber leider oft auch komplexer.

Womit auf Seite 10 der grobe Unsinn von ganz am Anfang wieder aufgegriffen wurde.
Zyklische Evolution FTW