Tribonacci Folge Rekursiv

[GAZ]

Nabend zusammen,
Sitze gerade an einer Übung soll hier die Tribonacci-Zahl an n-ter Stelle rekursiv berechnen, was ich so weit auch hinbekommen habe.
Mein Problem liegt jetzt in der Ausgabe und zwar soll ich auch alle vorangegangenen Zahlen der Tribonacci-Folge mit ausgeben.

Rekursive Methoden sind für mich noch ziemlich neu das schreiben selber finde ich nicht so schwer, verstehe nur noch nicht so ganz wie ich mir mehrere Werte von der rekursiven Methode übergeben bzw. ausgeben lasse, ein allgemeiner Tipp wäre auch schon super weil mir noch mehr solcher Aufgaben bevor stehen.

Hier erstmal das Programm:

Tribonacci Rekursiv

---

public class Tribonacci {

public static void main (String[] args) {

int n = Integer.parseInt(args[0]);
System.out.println(tribonacciRecursive(n));
}

private static int tribonacciRecursive(int n) {
int an=0;

if (n==0 || n==1) {
return 0;
}
if (n==2) {
return 1;
} else {
an = tribonacciRecursive(n-1)+tribonacciRecursive(n-2)+tribonacciRecursive(n-3);
return an;
}
}
}

So also übergebe ich nun z.B. n=8, soll nicht nur "24" ausgegeben werden, sondern alle Tribonacci-Zahlen bis "an=24" im Fall von n=8 also "0,0,1,2,4,7,13,24".
Hat da vielleicht jemand einen Tipp für mich? Muss ich was in der Main-Methode oder in der tribonacci-Methode ändern?

 

[DrPils]

Dann wuerde ich die Tribonacci Folge in eine Arraylist speichern und diese ausgeben, hatte mal aehnliches mit der Fibonacci folge gemacht 😉 😛

ArrayList (Java Platform SE 7 )

 

[GAZ]

Ok und das geht auch rekursiv? Bevor ich mich jetzt dran mache und ich dann die Aufgabenstellung nicht erfüllt habe? 😀
Vielen Dank schonmal.

 

[kneitzel]

Also das ist jetzt so nicht ganz so einfach aus meiner Sicht, denn du rufst die einzelnen Stellen ja mehrfach auf.

Daher wäre es notwendig zu speichern, ob ein Wert bereits ausgegeben wurde und ein Wert darf nur ausgegeben werden, wenn es an der Reihe ist. Also muss der Vorgänger bereits ausgegeben worden sein ...

Aber wenn man eh schon so ein Array hat, dann kann man das auch gleich mit Werten füllen. Dann wird ein berechneter Wert im Array gespeichert. Dazu z.B. ein Integer Array erstellen, Die ersten Werte setzen (also die ersten zwei 0er), der Rest bleibt null. Und die Methode schaut dann: Ist das Feld null? -> Rekursiver Aufruf und dann Ergebnis in Array schreiben. Ansonsten Wert aus Array zurück geben.

Das ist dann auch eine massive Optimierung bezüglich Laufzeit.

 

[GAZ]

Ok vielen Dank dann versuch ich mal mein Glück!

 

[GAZ]

Also das ist jetzt so nicht ganz so einfach aus meiner Sicht, denn du rufst die einzelnen Stellen ja mehrfach auf.

Daher wäre es notwendig zu speichern, ob ein Wert bereits ausgegeben wurde und ein Wert darf nur ausgegeben werden, wenn es an der Reihe ist. Also muss der Vorgänger bereits ausgegeben worden sein ...

Aber wenn man eh schon so ein Array hat, dann kann man das auch gleich mit Werten füllen. Dann wird ein berechneter Wert im Array gespeichert. Dazu z.B. ein Integer Array erstellen, Die ersten Werte setzen (also die ersten zwei 0er), der Rest bleibt null. Und die Methode schaut dann: Ist das Feld null? -> Rekursiver Aufruf und dann Ergebnis in Array schreiben. Ansonsten Wert aus Array zurück geben.

Das ist dann auch eine massive Optimierung bezüglich Laufzeit.

dazu müsste ich dann die if-Abfrage in der tribonacci-Methode für n=0 und n=1 weglassen oder sehe ich das falsch?

 

[GAZ]

Also das ist jetzt so nicht ganz so einfach aus meiner Sicht, denn du rufst die einzelnen Stellen ja mehrfach auf.

Daher wäre es notwendig zu speichern, ob ein Wert bereits ausgegeben wurde und ein Wert darf nur ausgegeben werden, wenn es an der Reihe ist. Also muss der Vorgänger bereits ausgegeben worden sein ...

Aber wenn man eh schon so ein Array hat, dann kann man das auch gleich mit Werten füllen. Dann wird ein berechneter Wert im Array gespeichert. Dazu z.B. ein Integer Array erstellen, Die ersten Werte setzen (also die ersten zwei 0er), der Rest bleibt null. Und die Methode schaut dann: Ist das Feld null? -> Rekursiver Aufruf und dann Ergebnis in Array schreiben. Ansonsten Wert aus Array zurück geben.

Das ist dann auch eine massive Optimierung bezüglich Laufzeit.

Habs geschafft etwas anders als du beschrieben hattest,
Musste garnicht alles rekursiv machen ist mir dann aufgefallen 🤦‍♂️ hab in der main-Methode dann einfach ein Array mit einer for-Schleife mit den Tribonacci-Zahlen gefüllt.
Hast mir aber den richtigen Gedankenanstoß gegeben vielen Dank!

 

[kneitzel]

Ok und das geht auch rekursiv? Bevor ich mich jetzt dran mache und ich dann die Aufgabenstellung nicht erfüllt habe? 😀

Musste garnicht alles rekursiv machen ist mir dann aufgefallen 🤦‍♂️ hab in der main-Methode dann einfach ein Array mit einer for-Schleife mit den Tribonacci-Zahlen gefüllt.

Du musst aufpassen, denn wenn die Bedingung ist, dass Du rekursiv alles berechnest, dann ist deine Lösung ggf. nicht mehr wirklich toll.

Du kannst natürlich so vorgehen, dass Du das Array erstellst und dann iterativ befüllst. Aber bei einer Anforderung, es rekursiv zu machen, ist diese Aufgabenstellung ggf. nicht mehr erfüllt.

Das Array erstellen und dann mitgeben ist ok. Aber dann muss es wirklich sein:
- Ist der Wert im Array schon gespecheiert? -> Wert zurück geben.
- Sonst die normale Rekursion nutzen um den Wert zu berechnen. Dabei ändert sich nur, dass das Array mit übergeben wird. Das Ergebnis wird dann nach der Berechnung noch im Array eingetragen.

Dabei fällt mir aber auch gerade ein, dass es noch anders geht. Du willst ja die Reihe ausgeben, daher kannst Du einfach eine Methode schreiben, die als Parameter bekommt:
- drei Vorgänger (Integer, kann null sein).
- aktuelle "Tiefe"
- gewünschte "Tiefe".

Tribonacii(x) -> Tribonacii(null, null, null, 0, x)

Tribonacci(vorg3, vorg2, vorg1, x, y)
x>y -> keine Ausgabe
x==0 -> "0" + Tribonacii(null, null, null, x+1, y)
x==1 -> ", 0" + Tribonacii(null, null, null, x+1, y)
x==2 -> ", 1" + Tribonacii(0, 0, 1, x+1, y)
x==y -> ", " + (vorg3 + vorg2 + vorg1) + Tribonacii(vorg2, vorg1, (vorg3 + vorg2 + vorg1), x+1, y)

Das wäre dann ein Algorithmus zur Ausgabe der Reihe. Die Zahlen werden direkt ausgegeben und nicht gespeichert. Das Array entfällt somit.

==> Das ist der einfachste Ansatz und auf den kommt man ganz einfach, indem man sich einfach hin setzt und sich fragt: Wie würde ich denn diese Reihe auf ein Papier schreiben? Was brauchst Du um Zahl für Zahl zu schreiben? Die ersten drei Zahlen sind vorgegeben, für jede nächste Zahl braucht man die drei vorherigen, wie viele Zahlen man schon geschrieben hat und wie viele Zahlen gewünscht sind. (x und y noch entsprechend umbenennen! Im Code würde ich Variablen ordentliche Namen vergeben!)


Ansonsten fällt mir gerade auf: Die Liste für 8 ist doch falsch, oder? Du hast geschrieben:
"0,0,1,2,4,7,13,24".

Das wären zum einen nur die Werte von 0...7 und nicht bis 8. Und die 1 muss doppelt sein.
0, 0, 1 ist vorgegeben.
Dann kommt 0+0+1 = 1
Dann kommt 0+1+1 = 2
...
"0,0,1,1,2,4,7,13,24".

 

[LimDul]

Ich würde es so lösen, wenn es weiterhin komplett rekursiv sein soll:

public int tribonacciRekursiv(int n, boolean printValue) {
int returnValue = 0;
if (n==2) { returnValue = 1: }
else if (n>2) {
returnValue = tribonacciRekursiv(n-1, printValue)+tribonacciRekursiv(n-2, false)+tribonacciRekursiv(n-3, false);
}
if (printValue) { System.out.print(returnValue); }
return returnValue;
}

Einfach einen boolean Parameter mitschleppen, der angibt ob der Wert ausgeben werden soll. Der muss dann bei den rekusirven Aufrufen für n-2 und n-3 false sein, bei dem Aufruf mit n-1 muss der true sein, sofern er als true übergeben wurde.

 

[Blender3D]

So also übergebe ich nun z.B. n=8, soll nicht nur "24" ausgegeben werden, sondern alle Tribonacci-Zahlen bis "an=24" im Fall von n=8 also "0,0,1,2,4,7,13,24".

Du verwendest als Startwert 0, 0, 1
Hier eine rekursive und eine iterative Lösung.
Die iterative Lösung ist die Bessere, weil es nicht zu wiederholten Berechnungen der Vorgänger führt.
[CODE lang="java" title="Tribonacci" highlight="11-18"]import java.util.Arrays;

public class TestTribonacca {
public static void main(String[] args) {
int[] values = new int[8];
tribonacciRec(values, values.length);
System.out.println(Arrays.toString(values));
}

public static int tribonacciRec(int[] values, int n) {
int value = 0;
if (n == 2)
value = 1;
if (n > 2)
value = tribonacciRec(values, n - 1) + tribonacciRec(values, n - 2) + tribonacciRec(values, n - 3);
if (n < values.length)
values[n] = value;
return value;
}

public static String tribonacci(int n) {
int[] predecessor = { 0, 0, 1 };
StringBuffer out = new StringBuffer("0 0 1 ");
for (int i = 2; i < n; i++) {
int current = predecessor[0] + predecessor[1] + predecessor[2];
predecessor[0] = predecessor[1];
predecessor[1] = predecessor[2];
predecessor[2] = current;
out.append(current + " ");
}
return out.toString();
}
}
[/CODE]

 

[kneitzel]

Die iterative Lösung ist die Bessere, weil es nicht zu wiederholten Berechnungen der Vorgänger führt.

Das liegt aber auch nur am Ansatz der rekursiven Lösung. Ebenso kannst Du das, was Du iterativ gemacht hast, als rekursiven Algorithmus aufbauen. Das war ja, was ich in #8 beschrieben habe.

 

[Blender3D]

Das liegt aber auch nur am Ansatz der rekursiven Lösung. Ebenso kannst Du das, was Du iterativ gemacht hast, als rekursiven Algorithmus aufbauen. Das war ja, was ich in #8 beschrieben habe.

Damit hast du vollkommen recht. Und dein vorgeschlagener Ansatz entspricht wahrscheinlich der besten Lösung für die Aufgabenstellung.
Anzumerken sei hier nur noch, dass grundsätzlich bei diesem Beispiel die iterative Lösung die Besser ist. Die Rekursion belastet den Function Stack ohne den Vorteil einen kürzeren Code zu erhalten.
Durch @kneitzel 🙂 Input bedingt zwei verbesserte Varianten zum Vergleich.
[CODE lang="java" highlight="13-19,23-27"]import java.util.Arrays;

public class TestTribonacca {
public static void main(String[] args) {
int[] values = new int[9];
tribonacciRecKneizel(values, 0);
System.out.println(Arrays.toString(values));
values = tribonacci(8);
System.out.println(Arrays.toString(values));
}

public static void tribonacciRecKneizel(int[] values, int id) {
if (id >= values.length)
return;
if (id == 2)
values[id] = 1;
if (id > 2)
values[id] = values[id - 3] + values[id - 2] + values[id - 1];
tribonacciRecKneizel(values, ++id);
}

public static int[] tribonacci(int n) {
int[] values = new int[n + 1];
values[2] = 1;
for (int i = 3; i < values.length; i++)
values = values[i - 1] + values[i - 2] + values[i - 3];
return values;
}
}
[/CODE]