Java-Rekursion Verständnis

[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