Java-Rekursion Verständnis

[fishbone]

Hi Forum,

ich checke leider folgende Rekursion nicht:

public class Rekursion {

public static void main(String[] args) {
  for (int i=0; i<7; i+=2)
   System.out.println(f(i)+"");
 }

public static int f(int x) {
  if (x<1) return 1;
  return f(x-1) + f(x-2);

}

}

1. Die Schleife beginnt mit 0, die Methode gibt 1 zurück, da if zutrifft.
2. Variable i von der Schleife ist nun 2. Was passiert nun?

Er gibt return f(2-1) + f(2-2) zurück. Sprich, ruft er sich dann mit f(1)+f(0), also abgezogen (Minus) f(1) auf?

Würde er sich mit f(1) aufrufen, käme dann laut meiner Logik dann
return f(1-1) + f(1-2) heraus. Also f(f(0)+f(-1)

Grüße

[Vinzenz Mai]

Hallo,

ich checke leider folgende Rekursion nicht:

ich zitiere Cheatah, Zitat 225

"Um Rekursion zu verstehen, muss man zunächst Rekursion verstehen."

public class Rekursion {

ein schlechter Klassenname ;-) Fibonacci wäre passender, auch wenn sie fehlerhaft implementiert ist.

public static void main(String[] args) {
  for (int i=0; i<7; i+=2)
   System.out.println(f(i)+"");
}

// fehlerhafte Methode

public static int f(int x) {
  if (x<1) return 1;
  return f(x-1) + f(x-2);

}

}

Ein nettes Beispiel für eine elegante rekursive Definition, die zu ineffizientem Laufzeitverhalten führt. Wer die Fibonaccifolge rekursiv implementiert, ist selbst schuld (wenn es nicht eine Vorgabe ist).

1. Die Schleife beginnt mit 0, die Methode gibt 1 zurück, da if zutrifft.
2. Variable i von der Schleife ist nun 2. Was passiert nun?

Er gibt return f(2-1) + f(2-2) zurück. Sprich, ruft er sich dann mit f(1)+f(0), also abgezogen (Minus) f(1) auf?

Würde er sich mit f(1) aufrufen, käme dann laut meiner Logik dann
return f(1-1) + f(1-2) heraus. Also f(f(0)+f(-1)

Ja, ist halt bei dieser Methode so definiert. Ich schreibe es für mich etwas lesbarer:

public static int f(int x) {
    if (x < 1) {
        // Beim Aufruf mit Argument 0 oder -1 wird dieser Zweig ausgeführt,
        // d.h. 1 zurückgegeben. Hier endet die Rekursion.
        return 1;
    }
    return f(x-1) + f(x-2);
}

Bei dieser "Variation" der Fibonacci-Folge ist die Abarbeitung wie folgt

f(0): Es wird der if-Zweig abgearbeitet: 1
f(1): Im ersten Durchlauf: Aufruf von f(0) + f(-1)
      zweiter Durchgang für f(0): 1
      zweiter Durchgang für f(-1): 1
      Ergebnis: 2

f(2): Im ersten Durchlauf: Aufruf von f(1) und f(0)
      im zweiten Durchlauf für f(1): Aufruf von f(0) und f(-1)
          im dritten Durchlauf für f(0): 1
          im dritten Durchlauf für f(-1): 1
      im zweiten Durchlauf für f(0): 1

f(3): Im ersten Durchlauf: Aufruf von f(2) und f(1)
      Im zweiten Durchlauf für f(2): Aufruf von f(1) und f(0)
          im dritten Durchlauf für f(1): Aufruf von f(0) und f(-1)
              im vierten Durchlauf für f(0): 1
              im vierten Durchlauf für f(-1): 1
          im dritten Durchlauf für f(0): 1
      Im zweiten Durchlauf für f(1): Aufruf von f(0) und f(-1)
          im dritten Durchlauf für f(0): 1
          im dritten Durchlauf für f(-1): 1

...

Korrekt für die Fibonacci-Zahlen wäre übrigens:

public static int f(int x) {
    if (x < 1) {
        return 0;
    }
    if (x == 1) {
        return 1;
    }
    return f(x-1) + f(x-2);
}

Freundliche Grüße

Vinzenz

[fishbone]

Hi Vinzenz, vielen Dank für die schnelle und vorallem ausführliche Antwort ;)

"Um Rekursion zu verstehen, muss man zunächst Rekursion verstehen."

Ich gebe mein Bestes ;)

public class Rekursion {

ein schlechter Klassenname ;-) Fibonacci wäre passender, auch wenn sie fehlerhaft implementiert ist.

War nur eine Klausuraufgabe von unserem Proff.

public static void main(String[] args) {
  for (int i=0; i<7; i+=2)
   System.out.println(f(i)+"");
}

// fehlerhafte Methode

public static int f(int x) {
  if (x<1) return 1;
  return f(x-1) + f(x-2);

}

}

[..]

f(2): Im ersten Durchlauf: Aufruf von f(1) und f(0)
      im zweiten Durchlauf für f(1): Aufruf von f(0) und f(-1)
          im dritten Durchlauf für f(0): 1
          im dritten Durchlauf für f(-1): 1
      im zweiten Durchlauf für f(0): 1

Das Ergebnis ist:
1
3
8
21

Die Methode "f" ruft sich ja immer wieder selber auf. D.h., wenn die Bedigung "if (x<1) return 1;" zutrifft, gibt er am Ende nicht 1 zurück, sondern die Zahl, wie oft die Methode aufgerufen wurde ne.

Bei deinem Schema oben hätte er die Methode 3 mal aufgerufen. Dann passt es auch mit der Ausgabe. Bei f(4) dürfte er er dann wohl die Methode 8 mal durchlaufen. f(x-1) und f(x-2) natürlich gesondert betrachtet und zusammengezählt.

Hoffentlich hab ich es nun gerafft ;)

Grüße