rekursive template Funktionen ohne Parameter

kaffeekanne

Hallo,

ich habe eine rekursive Funktion, die möglichst keine Parameter haben soll, damit der Stack nicht überlaufen kann.

Beispiel:

static MyStruct *s;

void func()
{
// code using s which is set outside
func();
// recursive call
}

Aber ich möchte die Funktion als template für verschiedene Datentypen haben. Auch das geht.

Beispiel:

template <class T> class MyClass
{
...

}

template<class T> void func(MyClass<T> *s)
{
// code using s
func(s);
// recursive call
}

In letzterem Beispiel wird aber Stackplatz gebraucht und na ja, wenn func sich oft genug aufruft, ist der Stack alle. Nicht-rekursiv kann ich die Funktion nicht schreiben. Die Funktion wird so oft aufgerufen, dass wahrscheinlich jeder Stack überlaufen würde.

Beide Sachen gehen einzeln: kein Überlaufen und templates. Ich möchte aber beides haben, eine template Funktion, die keinen Stack, sondern nur heap belegt. Geht das irgendwie???

Grüße Jan

Th

Jede Funktion (egal ob Template oder nicht) benötigt zur Laufzeit Stackspeicher (auch ohne Parameter), nämlich für die Rücksprungadresse (es gibt zwar Compiler, welche eine selbstrekursive Funktion am Ende zu einem einfachen Jump eliminieren (komme gerade nicht auf den Namen), aber darauf würde ich mich nicht verlassen.

Außerdem benötigt jede rekursive Funktion eine Abbruchbedingung, weil sonst kannst du auch einfach "while(true) {};" schreiben.

Hundefutter

Ich weiß nicht, wie du dir das mit der Rekursion vorstellt, aber wenn deine rekursive Funktion keine Parameter hat, dann werden die Werte in ihr auch nicht von außen beeinflusst, was dazu führt, dass kein Rekursionsende eintreten kann und dann haste da ne schönen Mist...

Deine rekursive Funkion wird wahrscheinlich mit einer Fallunterscheidung arbeiten und da sollte es mindestens einen nicht-rekursiven Zweig geben und du kannst dann über die Parameter die Funktion dazu bringen, irgendwann diesen Zweig auszuführen und so die Rekursion abzubrechen..

Also ohne Parameter wird das mit der Rekursion schwierig...

MfG
Hundefutter

Simon2

Hundefutter schrieb:

Ich weiß nicht, wie du dir das mit der Rekursion vorstellt, aber wenn deine rekursive Funktion keine Parameter hat...

static int count = 100;

void f() {
   --count;
   if(count > 0) f();
}

Vielleicht zum Stack testen sinnvoll, aber ansonsten fällt mir auch nicht viel ein.

Gruß,

Simon2.

hustbaer

hm.
zuviel kaffee, zu wenig grüner tee?
lol, was bin ich doof...

tip: jede rekursive funktion lässt sich auch iterativ mit hilfe eines stacks implementieren. wenn du glaubst du hättest die ausnahme gefunden dann begründe bitte wieso du glaubst es liesse sich nur rekursiv implementieren.

Hundefutter

Simon2 schrieb:

static int count = 100;

void f() {
   --count;
   if(count > 0) f();
}

klar ist es möglich, mit globalen Variablen zu arbeiten, nur sollte man dies nur in äußersten Notfällen tun...

Am besten er versucht ne iterative Version zu finden und wenn er es nicht schafft, hilft bestimmt auch hier das Forum...

MfG
Hundefutter

kaffeekanne

Vielen Dank für alle Antworten. Das hat mir doch erheblich geholfen. Ich weiß nämlich jetzt, dass es so, wie ich wollte, nicht geht.

Jede rekursive Funktion braucht Stackspeicher, und sei es nur für die Rücksprungadresse. Da der Stack eines Programms im allgemeinen nicht dynamisch vergrößert werden kann und in der Regel viel mehr Heap als Stack zur Verfügung steht, muss ich wohl in den sauren Apfel beißen und aus meiner rekursiven Funktion eine iterative Variante machen. Ich hab nur keine Lust zu...

Sollte ich dabei noch Fragen haben, werde ich mich nochmals vertrauensvoll an euch wenden.

Simon2

Hundefutter schrieb:

Simon2 schrieb:
static int count = 100;

void f() {
   --count;
   if(count > 0) f();
}
klar ist es möglich, mit globalen Variablen zu arbeiten...

Mehr wollte ich nicht belegen. Dein Post klang halt so, als ob jede rekursive Funktion ohne Parameter zwangsläufig eine Endlosschleife sei.
Es sollte nur die "Machbarkeit", nicht die "Sinnhaftigkeit" belegen.
(globale Variablen sind dicht an Makros )

Gruß,

Simon2.

hustbaer

kaffeekanne schrieb:

Ich hab nur keine Lust zu...

Ah, jetzt ist mir alles klar

Tip: wenn du einen neuen Thread rausstartest kannst du die Stackgrösse mitgeben. Probiers einfach mal mit 100MB, das sollte leicht verfügbar sein, und is immerhin das 100fache vom Defaultwert. In dem Thread kannst du dann die Funktion laufen lassen.
Eine andere Möglichkeit wäre die Stackgrösse für das ganze Programm zu ändern (Linkereinstellung), bloss dann bekommt leider *jeder* Thread der mit "Stackgrösse = default" angelegt wird soviel Stack, was u.U. auch doof sein könnte.

Konrad Rudolph

kaffeekanne schrieb:

muss ich wohl in den sauren Apfel beißen und aus meiner rekursiven Funktion eine iterative Variante machen. Ich hab nur keine Lust zu...

Dann poste doch mal das Problem, vielleicht fällt jemanden doch eine elegante rekursive Lösung ein.