Stack vergrößern?

BorisDieKlinge

Gibt es ne möglichkeit die Größe des Stacks zu verändern, damit ich eine tiefere Rekursion hin bekomme?

this-*gt*that

Bei den meisten Compilern kann man das einstellen. Beim Visual C++ gehts z.B. per /F Schalter.

BorisDieKlinge

wenn das programm dann release compiliert wird, wird die stackgröße dann extra für die exe übernommen?

Und was ist die F Taste? Hat das konsequenzen bzw. nachteile wenn ich ihn vergrößere? Wie groß ist der Stack standartmäßig?

BorisDieKlinge schrieb:

Gibt es ne möglichkeit die Größe des Stacks zu verändern, damit ich eine tiefere Rekursion hin bekomme?

mach aus der rekursion was iteratives

BorisDieKlinge

hatte ich schon.. aber ist zu langsam:) rekusiv ist das ding um den faktor 10-11 mal schenller (EDIT: als der iterator von std:list)

EDIT: Kann geschlossen werden:)

Du kannst den rekursiven Algorithmus in einen iterativen umbauen. Du musst nur den Callstack in einem eigenen Stack nachbauen und anstatt Funktionsaufrufen eine Schleife. Der eigene Stack legt dann seine Daten auf dem Heap ab. Dann bleibts eigentlich genauso schnell.

Badestrand

Evtl lässt sich bei dem rekursiven Algo auch ein Parameter sparen oder so?

BorisDieKlinge

@nogood: Aus reiner Interesse, könntest mir mal ein beispiel machen?

hustbaer

BorisDieKlinge schrieb:

@nogood: Aus reiner Interesse, könntest mir mal ein beispiel machen?

Keine Garantie dass der Code 100% funktioniert, aber das Prinzip sollte klar sein:

int sum_tree(node const* n)
{
    if (!n)
        return 0;
    else
        return n->value + sum_tree(n->left_child) + sum_tree(n->right_child);
}

// ->

int sum_tree(node const* n)
{
    std::vector<std::pair<node const*, int> > stack;
    stack.push_back(std::make_pair(n, 0));

    int accu = 0;

    while (!stack.empty())
    {
        std::pair<node const*, int>& state = stack.back();

        switch (state.second)
        {
        case 0:
            // fresh node
            if (state.first == 0)
            {
                // null pointer -> "return"
                stack.pop_back();
            }
            else
            {
                // add this value
                accu += state.first->value;

                // "recurse" left_child
                state.second = 1;
                stack.push_back(std::make_pair(state.first->left_child, 0));
            }
            break;

        case 1:
            // this node's value has already been accounted for and
            // left_child has already been visited

            // "recurse" right_child
            state.second = 2;
            stack.push_back(std::make_pair(state.first->right_child, 0));
            break;

        case 2:
            // this node's value has already been accounted for and
            // left_child has already been visited
            // right_child has already been visited
            stack.pop_back();
            break;
        }
    }

    return accu;
}

Wenn du nur einen Rekursiven Aufruf ganz am Ende der Funktion hast ("tail recursion") lässt sich das ganze auch ohne Stack machen.