Rekursion: Sekunden berechnen

[wolfheart]

Hallo, wie könnte man folgende Rekursion umschreiben damit die Funktion schneller und effizienter arbeitet? Nämlich bei n = 45 dauert die Prozedur schon ca. 30 Minuten:

public class Q {

	public static void main(String[] args) {

	System.out.print("Geben Sie ein Zahl ein: ");
	int n = readInt();
	System.out.println("Q(" + n + ") = " + Q(n));
	}
	
	private static int Q(int n) {
		if (n == 1 || n == 2)
			return 1;
		else
			return Q(n - Q(n - 1)) + Q(n - Q(n - 2));
	}

	}

 

[SlaterB]

schreibe dir einen Cache, int[] cache der Länge n oder gleiche 10000,
wann immer du ein Q(n) berechnen musst, schaue erst darin nach, wenn vorhanden dann das zurückgeben,
sonst neu berechnen und erst speichern, dann zurückgeben,

so kannst du beliebig hohe Werte in Sekundenbruchteilen berechnen

Q(8999) = 4418


edit: abgesehen von StackOverflowError bei zu hoher Rekursionstiefe, dann darauf achten,
von 1 bis n in Reihenfolge zu berechnen,

bei n<=0 gibt eh ne Exception

 

[wolfheart]

ehm, wie mache ich das mit dem Cache?

 

[SlaterB]

na korrekt,

    private static int Q(int n)
    {

    // vor der Berechnung irgendwo nachschauen ob schon vorhanden

        int q = 0;
        if (n == 1 || n == 2)
        {
            q = 1;
        }
        else
        {
            q = Q(n - Q(n - 1)) + Q(n - Q(n - 2));
        }

   // vor der Rückgabe neuberechnten Wert abspeichern

        return q;
    }

verraten kann ich es kaum