Rekursion

_matze

Tim123 schrieb:

Also:
ich geh in zeile 4 --> if bedingung erfüllt, da 1 < 4 --> rekursion --> a = 2
und jetzt ruft die funktion sich solge auf bis a nichtmehr kleiner gleich 4 ist und gibt sie aus. (sprich 5)
Und ab hier komme ich nicht mehr weiter, da die 2te if-bedingung ja die gleich wie die erste ist...

Die 2. Bedingung ist aber im Durchlauf mit a=5 nicht erfüllt. Die Funktion endet also hier und du bist wieder im vorigen Aufruf (da ist a wieder 4). Und hier geht es nach dem rekursiven f()-Aufruf weiter. Zunächst wird also wieder printf aufgerufen. Und dann bist du wieder bei der 2. Bedingung, die diesmal erfüllt ist (4<=4). es wird also wieder f() aufgerufen, mit a=2*4. Und so weiter...

Ja schon, aber wo wird der Wert wieder auf 4 erniedrigt, wenn er erstmal auf 5 ist?

Ich glaub ich steh voll aufm Schlauch

Wenn sich a doch um eins auf 5 erhöht, dann treffen beide if-Bedinungen nicht mehr zu und die Funktion ist beendet oder?

_matze

Timo123 schrieb:

Ja schon, aber wo wird der Wert wieder auf 4 erniedrigt, wenn er erstmal auf 5 ist?

Das ist Rekursion. Du rufst die Funktion mit a=1 auf, und noch während diese Instanz der Funktion läuft (sie ist noch nicht beendet!), wird wiederum eine weitere Instanz aufgerufen, diesmal mit a=2. Wenn dieser Aufruf beendet ist, kommst du wieder an die Stelle, an der der Aufruf f(2,4) stattgefunden hat. Und dort ist a (quasi das lokale a) immer noch 1, das hat sich nie geändert.

Das sind alles lokale Variablen.
Die werden bei jedem Funktionsaufruf neu angelegt.
Und sind auch noch da wenn du wieder zurückgehst.

Beim Verlassen der Funktion werden sie wieder gelöscht.

Jede Instanz von f() hat ihre eigenen Variablen.

_matze

Timo123 schrieb:

Ich glaub ich steh voll aufm Schlauch

Wenn sich a doch um eins auf 5 erhöht, dann treffen beide if-Bedinungen nicht mehr zu und die Funktion ist beendet oder?

Ja, aber nicht alle Instanzen der Funktion. Der Aufruf mit a=4 ist noch nicht beendet.

Hmm ich versteh das noch nicht so ganz
Gibts evtl passende Seiten zum nachlesen? hab noch nichts aufschlussreiches gefunden

cooky451

Timo123 schrieb:

Hmm ich versteh das noch nicht so ganz
Gibts evtl passende Seiten zum nachlesen? hab noch nichts aufschlussreiches gefunden

Guck dir doch bitte einfach mal meinen Beitrag an:

cooky451 schrieb:

main() // ruft f mit den Werten 1 und 4 auf
->f(1, 4) // ruft f mit den Werten 2 und 4 auf
  ->f(2, 4) // ...
    ->f(3, 4)
      ->f(4, 4)
        ->f(5, 4)
          ->print(a) -> 5 // das print wird von der f Instanz aufgerufen, deren a = 5 ist.
        ->print(a) -> 4 // das print wird von der f Instanz aufgerufen, deren a = 4 ist.
          f(8, 4)
            print(a) -> 8
        print(a) -> 3
        f(6, 4)
          print(a) -> 6
...

Jede aufgerufene Funktion wird eingerückt, so kann man für jede Instanz der Funktion genau sehen welchen Wert a in ihr hat! Fertig, total einfach!
Am Ende ist dann jede Funktionsinstanz fertig, und du landest wieder bei main().

Du kannst natürlich auch noch nachlesen wie der Computer das macht, aber das verwirrt dich momentan vermutlich nur noch mehr.
http://en.wikipedia.org/wiki/Call_stack

_matze

Vielleicht würde es auch helfen, mal mit dem Debugger Schritt für Schritt mitzuverfolgen und sich dabei anzusehen, welchen Wert das lokale a gerade hat (was Aufschluss darüber gibt, in welcher Instanz man sich gerade befindet).

int f(int a, int max) {  // a =    max =
    if (a <= max)
        f(a+1,max);      // f(    ,    )
    printf("%d\n", a);
    if (a <= max)       
        f(2*a,max);     //  f(    ,    )
}

Du kannst das da oben ja mehrmals ausdrucken.

Dann nimmst du einen Ausdruck und schreibst die Werte darein.

Wenn ein neuer Aufruf von f() kommt, nimmst du einen neuen Zettel, legst in auf den anderen, schreibst die neuen Werte rein und gehst auch diesen durch.
Wenn ein print kommt schreibst du das auf ein Extrablatt.

Wenn du durch die Funktion durch bist, nimmst du den Zettel von deinem Stapel und legst ihn zur Seite.
Dann siehst du den vorhergehenden Zettel mit seinen Werten und arbeitest den weiter ab, so wie oben.

Erstmal Vielen Danke für euer Engagement !
Ich hab es glaub immer noch nicht so richtig drin, aber werde es morgen nochmal versuchen.
Evtl. steh ich einfach nur auf dem Schlauch und morgen versteh ich es dann ganz schnell

Vielen Dank Leute

It0101

Ich hab mich damals mit der Rekursion zu Beginn auch schwer getan. Es war halt Thema in der Schule und man musste es irgendwie raffen...

Du musst dir vorstellen, dass mit jedem Aufruf der Funktion eine neue Box angelegt wird. Vormals aufgerufene "Boxen" werden dabei nicht verändert oder beendet... das heißt selbst wenn du aus deiner Funktion die gleiche Funktion nochmal aufrufst, ist der erste Funktionsaufruf mit all seinen Variablen immernoch da und wird weitergeführt wenn du von deinem zweiten Funktionsaufruf zurückkehrst...

Mal dir das am Besten auf, wie Cooky das gezeigt hat. Das könnte dir wirklich beim Verständnis helfen.

Ich habs jetzt mit ein wenig Abstand verstanden

Ich stells mir einfach so vor, dass die eine Funktion solang pausiert bis die danach aufgerufene beendet wird.

SeppJ

Timo1213 schrieb:

Ich stells mir einfach so vor, dass die eine Funktion solang pausiert bis die danach aufgerufene beendet wird.

Das brauchst du dir gar nicht so vorzustellen, das ist genau das was passiert. Du solltest jedoch auch wissen, warum. Jedoch weiß ich auch nicht, was ich dazu noch mehr erklären könnte, was in diesem Thread nicht schon längst gesagt oder angedeutet wurde.

It0101

Timo1213 schrieb:

Ich stells mir einfach so vor, dass die eine Funktion solang pausiert bis die danach aufgerufene beendet wird.

Das ist mit jeder Funktion so....