Objekte der Rekursion auf den Heap legen?

freakC++

Hallo,
wenn ich eine rekursive Funktion habe, dann werden ja lokale Objekte angelegt, die voneinandern nichts "wissen". Kann man diese auch auf den Heap legene? Wenn ja wie?

Vielen Dank
lg, freakC++

Nexus

Wieso möchtest du das? Informationen werden bei rekursiven Aufrufen im Normalfall durch Parameter und Rückgabetypen durchgereicht. Dass die einzelnen Funktions-Stackframes voneinander nichts wissen, ist ja ein Grundprinzip der Rekursion (die innerste Rekursionsebene führt eine unabhängige Aktion durch, gibt die Resultate eine Ebene nach aussen weiter, diese verfährt wieder ähnlich, und so weiter).

freakC++

Ja, ich weiß, doch geht es mir hier um kein Programm, sondern ich will einfach nur das Wissen haben. Mich interessiert das nur! Daher will ich wissen, wie man soetwas machen kann!

Vielen Dank
lg, freakC++

Nexus

Okay, aber was hat das dann mit Rekursion zu tun? Oder weisst du generell nicht, wie mit dynamischer Speicherverwaltung umzugehen ist? Falls doch, was ist in einer rekursiven Funktion anders?

Stelle deine Frage wenn möglich etwas präziser.

freakC++

OK! Ich weiß, wie ich mit dynamischer Speicherverwalung umzugehen habe. Die Rekursion wird ja oft gemieden, da dadurch leicht
Programme abstürzen, da der Stack nicht mehr ausreicht. Da frage ich mich, ob es vielleicht besser ist, die Objekte gleich auf den Heap
zu legen und selbst zu verwalten und wieder zu löschen! Ich weiß halt nur nicht, ob das was bringt oder ob meine Rekursion dadurch
"zerstört" wird. Wenn das funktioniert, dann würde ich mich über ein Minibeispiel freuenn ;).

Vielen Dank
lg, freakC++

curry-king

Du könntest doch als Übergabeparameter Deiner rekursiven Funktion einen Zeiger übergeben, an den Du in jeder Rekursionsstufe ein neues Stück dynamischen Speicher anhängst und dort Deine Daten ablegst.

drakon

Das Problem bei Rekursion ist eher, dass ständig Funktionen aufgerufen werden und die Übergabeparameter werden dann auf den Stack gepusht. Und wenn man das lange genug macht (auch wenn innerhalb der Funktion kein Speicher angefordert wird) kommts eben zu diesem Stack Overflow.

Du holst also nicht unbedingt viel raus, wenn du die Daten, die du innerhalb einer Funtion benutzt dynamisch anforderst. Ein paar Calls später hast du wieder das gleiche Problem.

freakC++

Hallo,
curry-kings Lösung leuchtet mir eigentlich ein, doch drakon hat ja Einwände erhoben. Wenn ich als Parameter einen Zeiger übergebe, warum funktioniert das nicht? Oder habe ich dich, drakon, falsch verstanden? ICh dachte ursprünlich an das Paradebeispiel:

int fakultaet(int n)
{
 if (n == 1)
 {
  return 1;
 } 
 else 
 {
  return n * fakultaet(n-1); //das erste n kommt auf den Stack
 }

Wenn ich nun fakultaet(3) aufrufe, dann erhalte ich folgendes ergebnis:

3 * fakultaet(2)
3 * 2 * fakultaet(1)
3 * 2 * 1

Die einzeln stehenden Zahlen sind ja auf dem Stack. Wenn ich diese nun auf den Heap lege (mit Zeigern), dann könnte ich doch vielleicht besser damit umgehen. Oder bringt das nichts, weil ich den Heap ja erst wieder leeren darf, wenn das Ergebnis vorhanden ist und dann ja auch der Stack geleert würde?

Vielen Dank
lg, freakC++

drakon

Hmm. Das könnte man durchaus tun und auch was rausholen (teste das doch mal!). Allerdings hatte ich eher die Rücksprungaddressen im Kopf, die auf den Stack gelegt werden.
Ggf. Werde ich später selbst mal schauen, wie weit man mit Parameter und ohne gehen kann.

curry-king

Vielleicht gibt es ja C++ Compiler, die tail-recursions erkennen und dann zu einem iterativen Programm optimieren?

Dann müsstest du Dein Problem als Enderekursion formulieren, wenn das geht.

//EDIT
Aber dann kannst du es ja gleich iterativ machen