rekursive fkt und stack

lookias

hallo

hab ne frage zum speicher

wenn ich jetzt zb ne funkt zum addieren grosser zahlen schreibe

dann bietet es sich am besten an dies rekursiv zu machen

habe aber gelsen dass jeder aufruf der fkt dann speicher im stack verbraucht und da der relativ rar ist koennte das ja problemem geben

ein ausweg waere wohl das ganze ohne rekursion zu machen

ich finde aber die rekursiven fkt sehr viel einfacher und schoener

gibet ne moeglichkeit rek fkt ohne stack benutzung zu schreiben

gruss lookias

Michael E.

Ja, das geht mit manchmal Template-Metaprogrammierung (immer wenn du schon beim Kompilieren weißt, mit welchen Zahlen du rechnen willst, das wird bei dir wohl nicht der Fall sein). Das wird für dich aber noch zu schwer sein. Nimm doch lieber den Schleifenweg.

BTW: Funktion und Rekursion sind nicht so lang, dass man sie abkürzen muss.

lookias

ist das dann so dass man sich nen eigenen stack im heap anlegt?

also schreiben die profies solche sachen ohne rekursive funktionen ja?

Michael E.

Nö.

DEvent

normale, endrekursive, funktionen haben den nachteil des grossen speicherverbrauchs.
iterativ-rekursive funktionen verhalten sich wie normale schleifen, nur halt rekursiv. da ist der speicherverbrauch genau so gross wie bei einer schleife.
z.b.:

// endrekursive:
int fakultat(int n)
{
    if ( n == 1 ) return 1;
    return n*fakultat(n-1);
} 
// iterativ-rekursiv:
void fak(int n, int y)
{
    if ( n == 1 ) return y;
    fak(n-1, y * n);
}

ungetestet.
die iterativ-rekursiv kann man auch einfach in eine schleife umschreiben.

Ich denke dass es ganz auf das Problem drauf ankommt

z.b. ist manchaml rekursiv besser manchaml iterativ.

bei manchen sachen ist rekursiv schlechter bei manchen sachen ist iterativ schlechter, da es viel länger dauert.

Michael E.

newkid: Sag mal bitte ein Beispiel, wo rekursiv besser ist.

net 0

DEvent schrieb:

normale, endrekursive, funktionen haben den nachteil des grossen speicherverbrauchs.
iterativ-rekursive funktionen verhalten sich wie normale schleifen, nur halt rekursiv. da ist der speicherverbrauch genau so gross wie bei einer schleife.
z.b.:
// endrekursive:
int fakultat(int n)
{
    if ( n == 1 ) return 1;
    return n*fakultat(n-1);
} 
// iterativ-rekursiv:
void fak(int n, int y)
{
    if ( n == 1 ) return y;
    fak(n-1, y * n);
}

nene, beide verheizen den stack. mal angenommen die parameter werden über den stack übergeben (wie's ja oft gemacht wird), und ein parameter hat 4 bytes, die rücksprungadresse auch, dann verbraucht 'fakultät' 8 bytes und 'fak' 12. bei 'ner rekursionstiefe von 100 sind es bei fakultät 800 und bei fak 1200 bytes vom stack. auf pc nicht so schlimm aber auf kleineren systemen kann das schon der absturz sein.

Also - ich würd dafür die GMP benutzen: http://swox.com/gmp/

@Michael E.: Die Türme von Hanoi zu iterieren ist seeeehr umständlich. Generell gilt das für so ziemlich alle Algorithmen, die eine mehrfache Rekursion benutzen und für die es keine einfacheren, iterativen Alternativen gibt (wie z.B. bei den Fibonacci-Zahlen).

DEvent

Michael E. schrieb:

newkid: Sag mal bitte ein Beispiel, wo rekursiv besser ist.

mir fällt da spontan eine baum-struktur ein in der du dann durch die einzelnen elemente durchiterierst. rekursiv ist das kinderleicht, iterativ recht schwer.
allg. bei allen rekursiven datentypen sind rekursive fuktionen leichter zu implementieren.

@net: hast ja recht...

lookias

das ist interresant wusste ich garnet dass es da nen unterschied gibt ob man nu die funktion zurueckgibt

oder ob man die fkt einfach aufruft in dem prog also

sind nur die return(fkt) anweisungen stack belastend oder jeder fkt aufruf?