Rekursion in Endrekursion umwandeln?

[Plauzi92]

Hallo liebe Community,

habe mich hier gerade als letzten Ausweg registriert, da ich seit nun mehr 2 Tagen an einem Problem hänge und zu keiner Lösung komme.
Es geht um Rekursionen. Bei der Fakultätsfunktion verstehe ich die Endrekursion und kann sie auch nachvollziehen. Hier habe ich allerdings nun eine Aufgabe, bei der ich einfach nicht weiß wie ich da eine Endrekursion erstellen soll.

Die Aufgabe handelt von der Berechnung der Ansteckungswahrscheinlichkeit von verschiedenen Krankheiten.
Dazu soll ich diese Formel endrekursiv implementieren:
x(n) = x (n-1) + 2* x(n-3) - x(n-2)

Es gilt: x(0) = 2; x(1) = 5; x(2) = 8;

Eine rekursive Methode hab ich geschafft. Die sieht folgendermaßen aus:

public static int rekursion (int n) {

if (n==0 ) return 2;
if (n==1 ) return 5;
if (n==2 ) return 8;

else
return (rekursion(n-1) + 2* rekursion(n-3) - rekursion(n-2));
}


Ich weiß aber absolut nicht wie ich das mit einer Hilfsfunktion endrekursiv implementieren soll, da ich dadurch ja auch 2 Parameter machen muss, obwohl ich nur einen brauche.
Könnte mir da jemand helfen? Die Sache macht mich noch wahnsinnig.

Danke im Vorraus und Liebe Grüße!

 

[Xyz1]

MWn. ist es schon endrekursiv. Nur die 2 könntest du noch rausziehen und die Reihenfolge der Operanden ändern.

 

[Flown]

@DerWissende Nö ist nicht Endrekursiv. Das letzte was ausgeführt ist, sind die arithmetischen Funktionen (+*-). Davor werden noch die Rekursionen ausgwertet.

Also deine Endrekursive Hilfsmethode hat übrigens dann 4 Parameter. 1 Laufvariable und 3 Variablen als Schieberegister.

 

[DrZoidberg]

Schreibe das Ganze erst einmal als for Schleife. Mit drei Variablen für die 3 aktuellen Zahlen der Zahlenreihe und einer Zählervariablen. Danach kannst du das dann in eine Rekursion umwandeln.

 

[mariane]

Ist eigentlich nicht so schwer, du könntest z.B. das Thema auch bei den Fibonacci-Zahlen näher unter die Luppe nehmen, da werden nur zwei Variablen für die berechnung des neuen Wertes herangezogen. Bei deinem Beispiel hier sind es eben drei.
Beispielhaft könnte das wie folgt aussehen, wobei ich mal __ als Platzhalter für a, b und c benutzt habe. Natürlich an der richtigen Stelle, das sollte jetzt nicht so schwer für dich sein.

    private static int endrekursion(int n)
    {
        int a = 2, b = 5, c = 8, d;
        while( n-- > 0 ) {
            d = __ + 2 * __ - __;
            a = b;
            b = c;
            c = d;
        }
        return a;
    }

 

[mariane]

komisch, bisher noch kein Einspruch
korrekt wäre:

    public static void main(String[] args) {
        for (int i = 0; i < 30; i++) {
            System.out.println(endrekursion(i, 2, 5, 8));
        }
    }

    public static int endrekursion(int n, int a, int b, int c) {
        if (n-- == 0) {
            return a;
        }
        return endrekursion(n, b, c, c + 2 * a - b);
    }

 

[Flown]

Warum postest du die Lösung?