Tribonacci Folge Rekursiv

GAZ

Mitglied
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?
 
Zuletzt bearbeitet:
K

kneitzel

Gast
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

Mitglied
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

Mitglied
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!
 
Zuletzt bearbeitet:
K

kneitzel

Gast
Ok und das geht auch rekursiv? Bevor ich mich jetzt dran mache und ich dann die Aufgabenstellung nicht erfüllt habe? :D
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

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

Java:
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

Top Contributor
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]
 

Blender3D

Top Contributor
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]
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
S Abwandlung der Fibonacci Folge Java Basics - Anfänger-Themen 3
berserkerdq2 Wo geschieht der "Rücksprung, bei der rekursiven Folge Java Basics - Anfänger-Themen 5
sserio Längste Collatz-Folge Java Basics - Anfänger-Themen 11
D Grösste Zahl in einer Folge herausfinden. (ULAM) Java Basics - Anfänger-Themen 9
J Rekursive Folge (a=a-1) Java Basics - Anfänger-Themen 9
D Hofstäter Q Folge Java Basics - Anfänger-Themen 3
V Fibonacci Folge Java Basics - Anfänger-Themen 4
M Methoden Fibonacci-Folge Java Basics - Anfänger-Themen 6
J Fibonacci -Folge rekursiv berechnen Java Basics - Anfänger-Themen 18
S Negafibonacci Folge berechnen Java Basics - Anfänger-Themen 24
T Algortihmus: Kürzeste Folge zu einer Zahl Java Basics - Anfänger-Themen 40
G Harmonische Rekursive Folge Java Basics - Anfänger-Themen 3
M Fibonacci-Folge mit while-Schleife Java Basics - Anfänger-Themen 4
J Byte Folge erkennen Java Basics - Anfänger-Themen 5
A Gerade Terme der Fibonacci-Folge aufsummieren Java Basics - Anfänger-Themen 12
R Roboter - Helmich Folge 6 Java Basics - Anfänger-Themen 32
S rekursive folge verbessern Java Basics - Anfänger-Themen 2
H JOptionPane YES Option mit Folge? Java Basics - Anfänger-Themen 2
P Collatz-Folge mittels indirekter Rekursion Java Basics - Anfänger-Themen 8
X Problem mit Ducci-Folge Java Basics - Anfänger-Themen 7
S Fibonacci Folge Java Basics - Anfänger-Themen 34
B Element in Folge suchen Java Basics - Anfänger-Themen 7
L iterative und rekursive Folge Java Basics - Anfänger-Themen 20
N Folge verschiedener Nährwerte zur Kubikwurzel Java Basics - Anfänger-Themen 15
I Fibonacci-Folge , direkter Weg. Java Basics - Anfänger-Themen 5
J Wurzel mit einer Folge brechnen Java Basics - Anfänger-Themen 5
E Rekursive definierten Folge Java Basics - Anfänger-Themen 10
D Bit-Folge bearbeiten Java Basics - Anfänger-Themen 2
H Passwort Brute Force rekursiv Java Basics - Anfänger-Themen 7
1 Array rekursiv durchlaufen Java Basics - Anfänger-Themen 8
E Rekursiv Objekte erzeugen - geht das? Java Basics - Anfänger-Themen 2
Cassy3 Binäre Bäume Rekursiv durchlaufen und bestimmte Elemente Zählen Java Basics - Anfänger-Themen 6
R0m1lly Kombinationen aus int array rekursiv Java Basics - Anfänger-Themen 2
L Rekursiv gegebenes Passwort herausfinden. Java Basics - Anfänger-Themen 2
P9cman Char Index rekursiv finden Java Basics - Anfänger-Themen 4
B Methoden Rekursiv festellen, ob eine Zahl gerade-oft vorkommt oder nicht Java Basics - Anfänger-Themen 4
S Methoden Methodenaufruf rekursiv zählen Java Basics - Anfänger-Themen 4
B Array nach Wert prüfen rekursiv Java Basics - Anfänger-Themen 5
sashady Zahlen rekursiv zerlegen und Ziffern addieren Java Basics - Anfänger-Themen 38
jhCDtGVjcZGcfzug Fibonacci Zahlen rekursiv und iterativ Java Basics - Anfänger-Themen 21
H Binominalkoeffizient tail-rekursiv in java darstellen Java Basics - Anfänger-Themen 0
G Primzahlen von Rekursiv nach Iterativ Java Basics - Anfänger-Themen 6
A Ackermmanfunktion rekursiv Java Basics - Anfänger-Themen 4
A Binärbaum rekursiv durchsuchen und Referenz zurückgeben Java Basics - Anfänger-Themen 4
H Rekursiv Methode ausführen bei Kindern Java Basics - Anfänger-Themen 12
G Methode Rekursiv umschreiben Java Basics - Anfänger-Themen 8
L Jede zweite Ziffer entfernen (rekursiv) Java Basics - Anfänger-Themen 6
J Dateien in Verzeichnissen rekursiv auflisten wirft Exception Java Basics - Anfänger-Themen 4
D Pentagonale Nummern in Rekursiv Java Basics - Anfänger-Themen 14
O Enum Array Rekursiv abarbeiten Java Basics - Anfänger-Themen 44
E Weg-Suche-Problem rekursiv Java Basics - Anfänger-Themen 12
O Primzahl rekursiv mit einem Wert ohne i, wie? Java Basics - Anfänger-Themen 6
E Erste Schritte Potenz Negativ (rekursiv) Java Basics - Anfänger-Themen 2
O Rekursiv aufrufen Java Basics - Anfänger-Themen 2
F In List Rekursiv suchen Java Basics - Anfänger-Themen 12
F Iterativ in Rekursiv Java Basics - Anfänger-Themen 2
S Fibonacci Zahlen rekursiv Java Basics - Anfänger-Themen 1
L Rekursiv zwei Strings vergleichen Java Basics - Anfänger-Themen 3
B Fakultätsfunktion Rekursiv Berechnen aber mit Array Java Basics - Anfänger-Themen 10
B Wie kann ich Linien rekursiv zeichnen? Java Basics - Anfänger-Themen 4
kilopack15 Sin(x) rekursiv lösen Java Basics - Anfänger-Themen 17
T Rekursiv Tiefe eines binären Suchbaums ermitteln Java Basics - Anfänger-Themen 22
P Methoden Arrays.AsList kleinste Zahl ausgeben Rekursiv Java Basics - Anfänger-Themen 9
W A hoch N Rekursiv Java Basics - Anfänger-Themen 3
K Rechtecke rekursiv zeichnen Java Basics - Anfänger-Themen 20
V Quadrate rekursiv zeichnen Java Basics - Anfänger-Themen 7
M Fibonacci rekursiv mittels Cache Java Basics - Anfänger-Themen 17
E Binärbaum - von rekursiv zu iterativ Java Basics - Anfänger-Themen 10
Y Rekursiv Palindrom herausfinden Java Basics - Anfänger-Themen 5
B Fibonacci Zahlen rekursiv Array Java Basics - Anfänger-Themen 12
M String rekursiv Spiegeln mit Originalwort davor Java Basics - Anfänger-Themen 3
K Türme von Hanoi - Rekursiv. Java Basics - Anfänger-Themen 1
T MergeSort rekursiv programmieren Java Basics - Anfänger-Themen 8
M Zahlenpyramide rekursiv programmieren Java Basics - Anfänger-Themen 7
hello_autumn Potenz selber berechnen, Rekursiv. Java Basics - Anfänger-Themen 6
V Text wüerfeln-Rekursiv Java Basics - Anfänger-Themen 4
J Baum rekursiv durchlaufen Java Basics - Anfänger-Themen 2
D Münzverteilung Möglichkeiten | Rekursiv Java Basics - Anfänger-Themen 3
R Hanoi rekursiv lösen Problem Java Basics - Anfänger-Themen 1
D Rekursiv Kombinationen ausgeben klappt nur bei einer Wiederholung Java Basics - Anfänger-Themen 4
shiroX OOP String rekursiv zurückgeben Java Basics - Anfänger-Themen 6
Z Fibonacci rekursiv meine Erklärung stimmt so? Java Basics - Anfänger-Themen 2
S java rekursiv iterativ hilfee :s Java Basics - Anfänger-Themen 5
E Erste Schritte Pi, rekursiv Java Basics - Anfänger-Themen 6
A Frage Methode ggt Rekursiv Java Basics - Anfänger-Themen 5
E Hanoi-Varianten rekursiv Java Basics - Anfänger-Themen 2
P Hanoi rekursiv zu iterativ umbauen Java Basics - Anfänger-Themen 20
P Mittelwert rekursiv Java Basics - Anfänger-Themen 13
E Integral Rekursiv Java Basics - Anfänger-Themen 15
M MergeSort rekursiv Java Basics - Anfänger-Themen 2
D Ziffer in Zahl Rekursiv Java Basics - Anfänger-Themen 4
B Array rekursiv untersuchen Java Basics - Anfänger-Themen 21
I Rekursiv Java Basics - Anfänger-Themen 13
C Rekursiv Zahlenfolgen berechnen mit zwei Variablen Java Basics - Anfänger-Themen 5
K Rekursiv zu Literal Java Basics - Anfänger-Themen 12
R Verzeichnisse rekursiv nach Dateiduplikaten durchsuchen Java Basics - Anfänger-Themen 5
L File Tree rekursiv Java Basics - Anfänger-Themen 10
W Binomialkoeffizient iterativ/rekursiv Java Basics - Anfänger-Themen 2
X Addition rekursiv ohne Schleife Java Basics - Anfänger-Themen 10
M Sudoku Rekursiv lösen Java Basics - Anfänger-Themen 9

Ähnliche Java Themen

Neue Themen


Oben