Rekursion umwandlen (in lineare Rekursion)

[schlelia]

Hallo,
folgende Folge sollte ich rekursiv implementieren:

Das habe ich so auch getan. Nun soll ich aber daraus eine lineare Rekursion machen:

Meine Ideen sind bisher:

public static double fibDvE(GFK gfk, int n, double a, double b, int c) {
        for (int i = n; i > 0; i--) {
            if (i == n) fibDvEHelper(gfk, n, a, b, c, i, Double.NaN, Double.NaN, Double.NaN);
        }
        return 0;
    }
    public static double fibDvEHelper(GFK gfk, int n, double a, double b, int c, int i, double mem1, double mem2, double mem3) {
        gfk.logDvE(gfk, n, a, b, c, i, mem1, mem2, mem3);

        return 0;
    }

return 0 steht natürlich nur als Platzhalter da. Ich bin mir nicht ganz sicher wie ich dabei vorgehen soll. Kann mir vllt jemand helfen, das Problem zu verstehen?

 

[schlelia]

Gerade noch mal ein wenig optimiert:

public static double fibDvE(GFK gfk, int n, double a, double b, int c) {
        return fibDvEHelper(gfk, n, a, b, c, 0, Double.NaN, Double.NaN, Double.NaN);;
    }
    public static double fibDvEHelper(GFK gfk, int n, double a, double b, int c, int i, double mem1, double mem2, double mem3) {
        gfk.logDvE(gfk, n, a, b, c, i, mem1, mem2, mem3);
            if (i == n) {
                return;
            }
            return fibDvEHelper(gfk, n, a, b, c, i + 1, mem1, mem2, mem3);
    }

 

[schlelia]

Nochmal ein kleines Update:

public static double fibDvEHelper(GFK gfk, int n, double a, double b, int c, int i, double mem1, double mem2, double mem3) {
        gfk.logDvE(gfk, n, a, b, c, i, mem1, mem2, mem3);
            if (i == n) {
                return n;
            }
            mem1 = n;
            if (i >= c && i % 2 == 0) {
                if (c == 1) return a * mem1 + mem1;
                if (c == 2) return a * mem1 + mem2;
                if (c == 3) return a * mem1 + mem3;
            }
            if (i >= c && i % 2 != 0) {
                if (c == 1) return b * mem1 + mem1;
                if (c == 2) return b * mem1 + mem2;
                if (c == 3) return b * mem1 + mem3;
            }

            return fibDvEHelper(gfk, n, a, b, c, i + 1, mem1, mem1, mem2);
    }

Mir ist jetzt eingefallen, dass ich je nach dem welchen Wert c hat, mem1, mem2 oder mem3 in die Formel einsetzen kann. Aber irgendwie funktioniert das noch nicht weiter

 

[mihe7]

Ok, das ist etwas komplizierter. Erstmal herausfinden, wie die Abbruchbedingung lautet.

Es soll F_n berechnet werden, wobei der rekursive Aufruf das Folgenglied F_i berechnet. Nehmen wir mal an, ergebnis wäre der Wert des Folgenglieds F_i. Die Rekursion endet, wenn i == n gilt und als Ergebnis würde ergebnis zurückgegeben. Offensichtlich muss ergebnis vor der Rückgabe berechnet werden.

Berechne ergebnis (also den Wert des Folgeglieds F_i)
Falls i == n
    gib ergebnis zurück
Sonst
    ...

Was passiert im Sonst-Fall? Natürlich muss hier das Ergebnis des rekursiven Aufrufs zurückgegeben werden.

Wenn wir uns die Formel ansehen und beachten, dass c einen Wert zwischen 1 und 3 annehmen kann, dann ist klar, dass bei der Berechnung von F_i der Parameter mem1 für F_{i-1}, mem2 für F_{i-2} und mem3 für F_{i-3} stehen muss. Bei F_{i+1} wäre mem1 also F_{i}, mem2 F_{i-1} und mem3 gleich F_{i-2}; und das ist, was uns interessiert, schließlich rufen wir nach der Berechnung des i-ten Folgeglieds ggf. die Berechnung des (i+1)-ten Folgeglieds auf:

Berechne ergebnis (also den Wert des Folgeglieds Fi)
Falls i == n
    gib ergebnis zurück
Sonst
    gib fibDvEHelper(..., i+1, ergebnis, mem1, mem2) zurück

Wie berechnet sich nun ergebnis? Naja, für den Fall 0 <= i < c ist ergebnis einfach i. Ansonsten kommt es zunächst darauf an, ob i gerade ist oder nicht und dann, welchen Wert c besitzt.

Falls i < c
    ergebnis := i
Sonst
    Falls i gerade, dann faktor := a, sonst faktor := b
    Falls 
        c == 1, dann summand := mem1
        c == 2, dann summand := mem2
        c == 3, dann summand := mem3
    ergebnis := faktor * mem1 + summand

Könnte passen.

 

[schlelia]

Ok, das ist etwas komplizierter. Erstmal herausfinden, wie die Abbruchbedingung lautet.

Es soll F_n berechnet werden, wobei der rekursive Aufruf das Folgenglied F_i berechnet. Nehmen wir mal an, ergebnis wäre der Wert des Folgenglieds F_i. Die Rekursion endet, wenn i == n gilt und als Ergebnis würde ergebnis zurückgegeben. Offensichtlich muss ergebnis vor der Rückgabe berechnet werden.

Berechne ergebnis (also den Wert des Folgeglieds F_i)
Falls i == n
    gib ergebnis zurück
Sonst
    ...

Was passiert im Sonst-Fall? Natürlich muss hier das Ergebnis des rekursiven Aufrufs zurückgegeben werden.

Wenn wir uns die Formel ansehen und beachten, dass c einen Wert zwischen 1 und 3 annehmen kann, dann ist klar, dass bei der Berechnung von F_i der Parameter mem1 für F_{i-1}, mem2 für F_{i-2} und mem3 für F_{i-3} stehen muss. Bei F_{i+1} wäre mem1 also F_{i}, mem2 F_{i-1} und mem3 gleich F_{i-2}; und das ist, was uns interessiert, schließlich rufen wir nach der Berechnung des i-ten Folgeglieds ggf. die Berechnung des (i+1)-ten Folgeglieds auf:

Berechne ergebnis (also den Wert des Folgeglieds Fi)
Falls i == n
    gib ergebnis zurück
Sonst
    gib fibDvEHelper(..., i+1, ergebnis, mem1, mem2) zurück

Wie berechnet sich nun ergebnis? Naja, für den Fall 0 <= i < c ist ergebnis einfach i. Ansonsten kommt es zunächst darauf an, ob i gerade ist oder nicht und dann, welchen Wert c besitzt.

Falls i < c
    ergebnis := i
Sonst
    Falls i gerade, dann faktor := a, sonst faktor := b
    Falls
        c == 1, dann summand := mem1
        c == 2, dann summand := mem2
        c == 3, dann summand := mem3
    ergebnis := faktor * mem1 + summand

Könnte passen.

Dann war ich ja garnicht so flasch.

public static double fibDvE(GFK gfk, int n, double a, double b, int c) {
        return fibDvEHelper(gfk, n, a, b, c, 0, Double.NaN, Double.NaN, Double.NaN);
    }

So ruf ich die Helpermethode außerdem auf. Ich glaube das mit dem mem1 ist noch ein Problem, da bei der ersten Ergebnisberechnung soetwas kommt: faktor * Double.NaN + summand

 

[schlelia]

Ok, das ist etwas komplizierter. Erstmal herausfinden, wie die Abbruchbedingung lautet.

Es soll F_n berechnet werden, wobei der rekursive Aufruf das Folgenglied F_i berechnet. Nehmen wir mal an, ergebnis wäre der Wert des Folgenglieds F_i. Die Rekursion endet, wenn i == n gilt und als Ergebnis würde ergebnis zurückgegeben. Offensichtlich muss ergebnis vor der Rückgabe berechnet werden.

Berechne ergebnis (also den Wert des Folgeglieds F_i)
Falls i == n
    gib ergebnis zurück
Sonst
    ...

Was passiert im Sonst-Fall? Natürlich muss hier das Ergebnis des rekursiven Aufrufs zurückgegeben werden.

Wenn wir uns die Formel ansehen und beachten, dass c einen Wert zwischen 1 und 3 annehmen kann, dann ist klar, dass bei der Berechnung von F_i der Parameter mem1 für F_{i-1}, mem2 für F_{i-2} und mem3 für F_{i-3} stehen muss. Bei F_{i+1} wäre mem1 also F_{i}, mem2 F_{i-1} und mem3 gleich F_{i-2}; und das ist, was uns interessiert, schließlich rufen wir nach der Berechnung des i-ten Folgeglieds ggf. die Berechnung des (i+1)-ten Folgeglieds auf:

Berechne ergebnis (also den Wert des Folgeglieds Fi)
Falls i == n
    gib ergebnis zurück
Sonst
    gib fibDvEHelper(..., i+1, ergebnis, mem1, mem2) zurück

Wie berechnet sich nun ergebnis? Naja, für den Fall 0 <= i < c ist ergebnis einfach i. Ansonsten kommt es zunächst darauf an, ob i gerade ist oder nicht und dann, welchen Wert c besitzt.

Falls i < c
    ergebnis := i
Sonst
    Falls i gerade, dann faktor := a, sonst faktor := b
    Falls
        c == 1, dann summand := mem1
        c == 2, dann summand := mem2
        c == 3, dann summand := mem3
    ergebnis := faktor * mem1 + summand

Könnte passen.

Okay grad noch was ausgebessert. War nur ein fehlendes else. Danke für deine Hilfe