Rekursionen

Tommy438

Hi,
wie ein paar Leute vielleicht schon gemerkt haben bin ich bei C++ etwas begriffsstuzig,ich bitte also darum das mir jmd an einem leicht verständlichen Beispiel Rekursionen erklärt.

Danke im Voraus!

otze

int fak(int i){//funktion zur berechnung der fakultät
    if(i==1){
        return 1;
    }
    else
    {
        return i*fak(i-1);
    }
}

ist so ziemlich das einfachste beispiel.

die fakultät von 5 ist 5*4*3*2*1
oder: fak(5)=5fak(4)
fak(4)=4fak(3)
fak(3)=3fak(2)
fak(2)=2fak(1)
fak(1)=1

und genauso arbeitet die funktion.

elise

if(fak**==**0){...
...
return i * fak(i-1);

otze

aiii da hat meine tastatur wieder versagt(zeichen klemmen manchmal)

lacht nicht, ich mein das ernst

ok, die sache mit dem mal zeichen...hmm...die führe auf ich zu hohe dosen cola light zurück

elise

auch beim + und dem * ?
*g*
no problem

Tommy438

Vielleicht noch etwas ausführlicher?Also zb wozu (i-1) etc.,

Danke sehr

Tommy438

Ah jetzt steht ein *

nman

Wie heißt es so schön?

In order to understand recursion, one must first understand recursion.

elise

schönes zitat

ansonsten gäbs da noch die kiste in der kiste in der kiste.. und wenn du unten bist, holst du dort was raus, und machst die kleinste wieder zu und dann die nächste und die nächste.. bist du wieder oben bist.

na ja, ein bild eben. geht auch mit den russischen püppchen.

Vielleicht noch etwas ausführlicher?Also zb wozu (i-1) etc.,

Ist das jetzt eine Frage nach dem Sinn oder wie man Rekursion anstellt?

Sovok

mir gefällt auch der lexikoneintrag

Rekursion
->siehe Rekursion

phlox81

Um Rekursion zu verstehen, muss man Rekursion verstanden haben :p

scrub

dadurch, daß die funktion beim aufrufen durch sich selbst komplett neu im speichersystem angelegt wird mitsamt allen variablen, ist rekursion erst möglich. sonst würde im gegebenen beispiel die variable i immer wieder überschrieben. aber: wie gesagt, bei jedem aufruf der funktion bekommt sie einen komplett eigenen bereich, der erst durch das beenden der funktion mitsamt der lokalen variablen wieder zerstört wird.

vereinbarst du aber eine variable static int i, so wird von allen aufrufebenen der funktion dieselbe variable angesprochen. mit anderen worten: das beispiel würde mit der statischen variablen nicht so funktionieren, dann wären änderungen im code nötig.

Tommy438

Beides!

Mit Rekursion können manche Probleme mit wenig Code gelöst werden, indem man das Problem in immer kleinere Häppchen teilt und diese bearbeitet, bis das Problem so klein ist, dass man es einfach lösen kann.

Bei Rekursion ruft eine Methode immer wieder sich selbst auf, bis eine Abbruchbedingung eintritt, daher muss zuerst immer auf diese Bedingung geprüft werden, sonst gibts nen Stackoverflow da die aufgerufenen Methoden im Stack gestapelt werden, bis der Abbruch statt findet

z.B. wird bei Fakultätsberechnung einfach die selbe Methode aufgerufen aber nicht mit der zu berechnenden Zahl, sondern eine kleinere.
Beim ersten Aufruf mit dem Wert 5 sieht es also so aus:

Fakultät(5) wird von außen aufgerufen
Fakultät(4) wird von sich selbst aufgerufen
Fakultät(3) wird von sich selbst aufgerufen
Fakultät(2) wird von sich selbst aufgerufen
Fakultät(1) wird von sich selbst aufgerufen

Bei Fakultät(1) tritt nun die Abbruchbedingung ein, weil Fakultät von 1 = 1.
Somit gibt der letzte Aufruf den Wert 1 zurück und wird jetzt erst ausm Stack entfernt.
Der vorletzte Aufruf rechnet mit der 1 und gibt 1*2 (also 2) zurück.
...
Der erste Aufruf gibt nun von den 1*2*3*4, also 24 und gibt 120 (24*5) zurück.

Allgemein gilt, dass man jede rekursive Lösung auch iterativ umsetzen kann.

interpreter

@echo off

Vellas

Hi!

Vielleicht helfen die meine Erklärungen aus folgendem Link weiter:
http://www.mycsharp.de/wbb2/thread.php?threadid=2044

Code-Hacker

Mis2com

Hi,

selber denken macht schlau, aber da ich gerade sowieso nichts zu tun habe...

int fak(int i){//funktion zur berechnung der fakultät
if(i==1){
return 1;
}
else
{
return i*fak(i-1);
}
}

Wir haben beispielsweise für i die Zahl 10.
Betrachten wir erst den else-Teil, der im Normalfall ausgeführt wird.
dort rechnet man natürlich 10*(9*8*7*6*5*4*32), uns interessiert aber einfach nur die 10... die rechnen wir einfach mal der Rekursion von 9
Denn 10(9*8*7*6*5*4*3*2) ist ja gleich 10*9!
In dem unteren Teil, wo die Rekursion von 9 berechnet wird, wird dann wiederum die Rekursion von 8 mit der 9 verrechnet.
Irgendwann kommt dann die Rekursion von 1 raus und hier muss man stoppen, sonst geht's ab, deswegen sagt man einfach return 1.
So, jetzt werden die ganzen returns tatsächlich multipliziert, d.h. erst kommt die 1, die wird dann in der oberen Funktion (von der Fakultät 2) damit verrechnet, also i*fak(i-1) wobei i = 2 und daher 2*fak(1) und da fak(1) = 1 2*1.
In der Funktion mit der Fakultät von 3 haben wir ja gesagt: i*fak(i-1), da i = 3 : 3*fak(2) und wir sahen ja oben, dass fak(2) = 2 * 1, daher 3*2*1
So, das lässt sich jetzt bis nach oben durchziehen.

MfG Eisflamme

Sternenstaub

also ich habe das so gelernt (zufälligerweise auch anhand der fak):

die fak von 4 = (fak von 3) * 4
die fak von 3 = (fak von 2) * 3
die fak von 2 = (fak von 1) * 2
die fak von 1 = 1

(aus diesem beispiel ist wahrscheinlich auch ersichtlich warum man sagt: "Um Rekursion zu verstehen muß man erst Rekursion verstehen.")

in einer rekursiven funktion gehst du diesen weg von "oben" nach "unten" durch und wenn du unten angekommen bist gibst du den wert an die "ebene" darüber weiter welche dann aus diesem wert einen neuen bildet und wiederum nach oben weiterreicht usw bis man wieder bei der ersten funktion angekommen ist.

um zu testen, ob du es wirklich verstanden hast kannst du ja mal eine rekursive funktion schreiben welche die zahlen von 1 bis n aufaddiert (z.B.: 1+2+3+4+5+6 = irgendwas, bin grad zu faul zum rechnen)

hoffe etwas geholfen zu haben,

sternenstaub

Ihr denkt alle viel zu viel iterativ.
Man beschreibt nicht mit Rekursion das "Wie?", sondern das "Was?".

mfg