Rekursive Funktion (Verständnisproblem)

kARRE

Hallo alle zusammen!

Ich habe es mir jetzt ungefähr 1000 bis 2500mal angeschaut und vberstehe es trotzdem nicht!

long blabla (long n)
{
if (n != 0)
{
return n * blabla(n-1);
}
return 1;
}

Die Funktion dient zum berechnen einer beliebigen Fakultät.
Nehemen wir an ich will 4! berechnen lassen, also 1*2*3*4:
Ich übergebe also nun den Wert 4.
Das ganze wird logischerweise in umgekehrter Reihenfolge abgearbeitet.
Was aber passiert, wenn n 0 ist?
Wenn ich das richtig sehe, steht irgendwo in meinem Programm sowas wie:

FakVier = blabla (4);

Wenn nun aber n 0 ist, wird der code nach der Bedingung fortgesetzt, wo offensichtlich "return 1;" steht.
Warum wird FakVier 24 und nicht 1?!

Klärt mich auf! Es ist der Stack, meine ich...was mir aber nicht hilft den Ablauf zu begreifen!

Im ersten Schritt wird ja n*blabla(n-1) zurueck gegeben. Das heisst aber, dass diese Funktion wiederum sich selber aufruft. Das macht sie, wie in Deinem Beispiel, von 4 abwaerts. Hier laeuft die Funktion entsprechend solange durch, bis irgendwann mal die Funktion mit "n-1=0" aufgerufen wird. In diesem Fall gibt die Funktion nur eine 1 zurueck und die Funktion an sich wird nicht mehr aufgerufen. Ist dieses der Fall, so wird die Rekursion quasi zurueck gerollt. Genau dann ist naemlich die Berechnung 1*2*3*4... und zu guter Letzt erhaeltst Du Deine Fakultaet. Zumindest ist das meine Vorstellung einer Rekursion. Fuer Kritik waere auch ich natuerlich dankbar.

kARRE

okay, aber was ist mit return 1; denn wenn FakVier 24 wird wohin geht dann die 1? Ich mein irgendwas muss doch damit passieren, oder nicht?

schmuessla

Erklärt ist es ja schon. Aber hier sieht man auch wie gefährlich rekursive Funktionen sein können. Teste mal mit n = 100.000, dann schmiert nämlich deine Applikation wegen stackoverflow ab. Hier lieber das problem mit einer schleife lösen.

EDIT: return 1 ist dein letztes *1.

wandert quasi wieder zurueck. Stell Dir das als Schachtel vor:

Du packst solange die anderen Schachteln aus, bis Du bei der Kleinsten angekommen bist, so dass Deine Funktion nur die 1 zurueck gibt. Dann gehst Du wieder in die vorherige Schachtel, wo dann die 1 mit der 2 multipliziert wird. Danach gehst Du in die naechste Schachtel, wo Deine 2 mit einer 3 multipliziert wird usw. Ersetz zum Beispiel mal die 1 mit einer 10. Dann erhaeltst Du das 10-fache der eigentlichen Fakultaet.

Sinthoras

kARRE schrieb:

long blabla (long n)
{
if (n != 0)
{
return n * blabla(n-1);
}
return 1;
}

Wenn du aufrufst:

blabla(4);

führt dich das zur Anweisung

// return n * blabla(n-1), mit n = 4
return 4 * blabla(3);

Bevor der Wert zurückgegeben werden kann, muss jetzt aber blabla(3) ausgewertet werden, was dann zu

// blabla(3)
return 3 * blabla(2);

führt.
Bevor jetzt blabla(3) den Wert an blabla(4) zurückgeben kann, muss erst blabla(2) ausgewertet werden, was

return 2 * blabla(1);

ergibt, was wiederum zu

return 1 * blabla(0);

führt.
Mit blabla(0) ist deine Rekursion beendet (denn blabla(0) ruft sich schließlich nicht mehr selbst auf, sondern gibt einfach 1 zurück).
Die Ergebnisse werden (rückwärts) an die jeweils aufrufende Funktion zurückgeliefert:

// blabla(1)
return 1 * 1;

an

// blabla(2)
// return 2 * blabla(1);
return 2 * 1;

an

// blabla(3)
// return 3 * blabla(2);
return 3 * 2;

an

//blabla(4)
// return 4 * blabla(3);
return 4 * 6

Fertig.
lg
Sinthoras

kARRE

Achso Ich könnte in diesem Fall also auch

if(n < 1)

anstelle von

if (n != 0)

benutzen, ohne das sich am Ergebnis was ändert.

Danke!

Jetzt hab ichs geschnallt! Das is in meinem Buch sowas von unzureichend erläutert...

Ich komm nich drauf klar, dass so viele und vor allem so schnell gepostet haben.

Nochmal Danke Leute!

pumuckl

kARRE schrieb:

Achso Ich könnte in diesem Fall also auch
if(n < 1)
anstelle von
if (n != 0)
benutzen, ohne das sich am Ergebnis was ändert.

Wenn du das '<' in ein '>' änderst passts fast.