rekursive Methode verstehe nicht!

[Cheese]

Hallo zusammen,

Ich lerne Java (Buch)seit kurzem. Ich hätte ein mal ne Frage warum bekomme ich wenn ich 9 einsetze 55 raus.
Dieser Quellcode ist aus dem Buch(Thema: rekursive Methoden). Leider wurde das im Buch nicht genau erklärt.
Ich hoffe ihr könnt mir helfen.

 public class fib 
{
static long fib (long n)
{
	if (n ==0) {
		return 1; }
	else if (n==1) {
	 return 1;
	} else 
		return fib(n-1) + fib(n-2);	// Das verstehe nicht er was der da macht
}
	public static void main(String[] args) 
	{
System.out.println(fib(9));		
	}
}

 

[Illuvatar]

Als erstes hab ich mal den Code ein bisschen lesbarer gestaltet, vielleicht hilft das ja schon:

public class Fibonacci
{
  static long fib (long n)
  {
    if (n == 0) {
      return 1;
    } else if (n == 1) {
      return 1;
    } else {
      return fib(n-1) + fib(n-2);
    }
  }
  public static void main(String[] args)
  {
    System.out.println(fib(9));
  }
}

Wenn nun [c]fib(9)[/c] aufgerufen wird, wird geprüft:
- 9 ist nicht gleich 0
- 9 ist auch nicht gleich 1
- also wird der else-Zweig ausgeführt und fib(8) + fib(7) zurückgegeben.
Die Werte von fib(8) und fib(7) müssen natürlich noch berechnet werden, die Methode wird also für diese beiden Werte wieder aufgerufen.

Das Ergebnis ist also die Fibonacci-Folge: Ein Folgenglied ergibt sich aus der Summe der beiden Folgenglieder davor. Um auf die 55 zu kommen, kannst du dir überlegen:
fib(0) = fib(1) = 1
fib(2) = fib(0) + fib(1) = 2
fib(3) = fib(1) + fib(2) = 3
fib(4) = fib(2) + fib(3) = 5
...

 

[Cheese]

Vielen Dank, ich habe das jetzt verstanden

 

[hüteüberhüte]

Auch hier würd ich wieder mal ein paar Ausgabeanweisungen reinschreiben, um sich die Methodenaufrufe zu verdeutlichen, siehe diese ähnliche Aufgabe: http://www.java-forum.org/hausaufgaben/133122-rekursionsaufgabe.html#post874590