Fibonacci rekursiv meine Erklärung stimmt so?

[Zoja]

Hallo Leute! Ich habe jetzt versucht die rekursive Variante für die Fibonacci Zahlen zu erstellen und habe es auch geschafft (mit Hilfe vom Internet) jedoch ist es mir wichtig, dass ich jeden Schritt verstehe, also so habe ich es gemacht:

Hoffe png war okay, hab da alles erklärt und Code ist ja mega simpel, habe ich es richtig verstanden?
Danke schön!

 

[stg]

Die Vorgehensweise scheinst du schon begriffen zu haben. Nur als Quelltextkommentar ist das in dieser Form natürlich unbrauchbar.

Nur als Ergänzung, falls es dich interessiert: Deine Lösung ist äußerst ineffizient, da du zahlreiche Zwischenergebnisse viel öfter berechnest, als du eigentlich musst. Da kann man durch ein paar Tricksereien einiges herausholen. Aber wenn es dir nur darum geht erst mal überhaupt zu verstehen, wie solche Rekursionen ablaufen, dann kannst du das getrost ignorieren.

 

[blux]

Das ist eine Lösung ja, aber keine besonders gute. Dadurch das du in der Rekursion zwei mal die fibo Methode aufrufst, baut deine Rekursion einen Baum auf (Baumrekursion), der exponentiell wächst. Errechne mal mit deiner Rekursion den Fibonacci von 3000 (Besser nicht, denn das Ergebnis würdest du in deiner Lebenszeit nicht mehr zur Gesicht bekommen).

Besser lässt sich das lösen, in dem du eine Endrekursion verwendest. Wenn du dir ein Blatt Papier nimmst und den Fibonacci von Hand ausrechnest, ähnelt diese Vorgehensweise der Endrekursiven. Per Hand würdest du ja auch niemals mehrere parallel Rechnungen aufbauen - du hast also bereits schriftlich den besseren Algorithmus gefunden. Mit der Endrekursiven Lösung ist dann auch die Berechnung des 3000'ten Fibonacci je nach Rechner ein Aufwand von Sekunden.

	public static long fib(int n) {

		return fib(n,0,1);	
	}
	
public static long fib(int n , int a , int b) {

		return (n==0)
				? a
			    : fib(n-1, b , a+b);
		}
		
	
public static void main(String[] args) {
		System.out.println(fib(3000));
      }