Rekursionen

[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!

[Airdamn]

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

[grenouille_unreg]

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

mfg

[Helium]

Wenn du versuchst rekursiv zu arbeiten, dann musst du immer nur darüber nachdenken, wie das aktuell zu bearbeitende Element bearbeitest. Über die Berechnung aller vorherigen Elemente machst du dir keine Gedanken. Allerdings muss es immer mindestens ein Element geben, das gesondert behandelt wird.

Die Fakultät ist da ein schönes Beispiel. Die Fakultät von 0 ist 1. Das ist unser besonders zu behandelndes Element. Die Fakultät von einer belibigen anderen natürlichen Zahl (jaja, 0 ist keine natürliche Zahl, aber das ist jetzt mal egal) berechnet sich aus dem Produkt aus der Zahl und der Fakiltät aus der um 1 kleineren Zahl.

0! = 0
n! = n * (n-1)!

Über das berechnen der Fakultät der nächst kleinere Zahl machst du dir einfach keine Gedanken. Du hast ja schon beschreiben, wie sich die Fakulät berechnen lässt. Dass dazu wiederum eine Fakultät nötig ist, interessiert nicht.
Das muss dann nurnoch in Code ausformuliert werden.

unsigned fakultaet (unsigned n) 
{
   if (n==0)
      return 1; 
   else 
      return n * fakultaet (n-1); 
}

Naja, C++ ist sicherlich nicht die schönste Sprache, um sowas zu Forumlieren.
Wenn du dich ernsthafter mit dem Thema Rekursion befassen willst, solltest du mal in eine funktionale Sprache reinschnuppern.

fakultaet 0 = 0
fakultaet n = n * fakultaet (n - 1)

[Korbinian]

heliums beispiel ist gut:
der springende punkt ist eben, einen basisfall (bei fakultät i == 0) und einen rekursionsfall zu haben. der rekursionsfall führt immer einen schritt richtung basisfall. scheme oder prolog sind hier viel hübscher

%prolog
fak(0, 1). %Fakultät von 0 ist 1
fak(N,F) :- N > 0, N1 is N-1, fak(N1,F1), F is N*F1. 
%bei N>0 solange 1 abziehen, biss man im basis fall ist, dann lösst sich alles in wohlgefallen auf :)

[Tommy438]

Danke für die vielen Posts!

[Helium]

@Korbinian: Du findest das Prologbeispiel tatsächlich schöner, als mein Haskell-Beispiel? Das kann ich jetzt nicht ganz nachvollziehen.