Frage zum Programmablauf

[Chri]

Hallo !

Ich habe ein rekrusives Programm geschrieben das die Fibonaccizahl ausgibt, hier der Code:

public static int fibonacci (int n) {
	if (n == 0 || n == 1) return 1;
	else {
		int a = fibonacci (n-1);
		int b = fibonacci (n-2);
		int y = a+b;
		return y;
	}

Das Programm funktioniert einwandfrei, aber ich verstehe den Ablauf nicht.

   int a = fibonacci (n-1);
            int b = fibonacci (n-2);

Warum werden diese 2 Variablen nicht so lange überschrieben bis sie den Wert 1 haben ??

z.B. Wenn ich die f(4) will -> a = fibonacci (3); a = fibonacci (2); a = fibonacci (1) = 1;

Dann müsste doch immer 2 rauskommen (a+b).

Kann mir das jemand erklären oder hat jemand einen Link über diesen Algorithmus ?

lg Chris

 

[Leroy42]

Warum werden diese 2 Variablen nicht so lange überschrieben bis sie den Wert 1 haben ??

Weil es in jeder Aufrufstufe der Methode zwei völlig
unterschiedliche Variablen a und b sind.

Oder anders gesagt:

Bei einem rekursiven Aufruf existieren mehrere
der Variablen a und b gleichzeitig.

 

[SlaterB]

jede Variable gilt nur lokal für eine Ebene, für eine Operationsdurchführung,
was in einem anderen Teil des Programms passiert, ist egal


int a = fibonacci (2); ist 2, unabgängig davon, was a in anderen Aufrufen der fibonacci-Operation lokal für einen Wert hat

 

[Guest]

z.B. Wenn ich die f(4) will -> a = fibonacci (3); a = fibonacci (2); a = fibonacci (1) = 1;

f(4) -> a=fibonacci(3)+ ->a=fibonacci(2) -> a=fibonacci(1) = 1
+ b=fibonacci(0) = 1
+ b=fibonacci(1) = 1
+ b=fibonacci(2) -> a=fibonacci(1) = 1
+ b=fibonacci(0) = 1

daraus folgt dann f(4) = 5

 

[Leroy42]

f(4) = 5, das ist richtig. aber deine Erklärung mit den a's und b's ist eher verwirrend.

Betrachte besser folgendes, gleichwertiges Programm:

public static int fibonacci (int n) { 
  if (n == 0 || n == 1)
    return 1; 
  else
    return fibonacci(n-1)+fibonacci(n-2); 
}

oder

public static int fibonacci (int n) { 
  return (n == 0 || n == 1) ? 1 : fibonacci(n-1)+fibonacci(n-2); 
}

f(4)
= f(3) + f(2)
= f(2)+f(1) + f(1)+f(0)
= f(1)+f(0)+f(1) + f(1)+f(0)
= 1+1+1 + 1+1
= 5

 

[Chri]

Vielen vielen dank !! jetzt versteh ichs endlich ^^

Eure Antworten waren sehr hilfreich!