• Wir präsentieren Dir heute ein Stellenangebot für einen Java Entwickler - m/w/d in Augsburg, München, Stuttgart oder Bamberg. Hier geht es zur Jobanzeige

Rekursive Java-Methode

M

Moemanyy

Mitglied
Hallo liebe Javafreunde,

ich habe hier eine rekursive Java-Methode, zu einer Aufgabe. Ich glaube, hier findet sich bestimmt jemand der das überprüfen kann.

Aufgabe)

Sei f: IN->IN eine Funktion, die folgendermaßen rekursiv definiert ist:
f(1)=1;f(2)=2 sowie
f(n)=4⋅f(n−1)−f(n−2), falls n>2.
Schreiben Sie eine rekursive Java-Methode, die zu einer gegebenen natürlichen Zahl den Funktionswert f(n) berechnen. eine main-Methode soll nicht beschreiben werden.

Antwort)

public class f{

public static int f(int n){
if (n==1)
return 1;
else if (n==2)
return 2;
else
return 4⋅f(n−1)−f(n−2);
}
}

Wäre super wenn mir jemand sagen würde ob ich alles richtig gemacht habe.

Mit freundlichen Grüßen
Moemanyy
 
H

httpdigest

Top Contributor
In Java gibt es keinen Operator mit dem Bild/Zeichen '⋅', somit kompiliert der Code nicht. Du meinst ja sicher den Multiplikationsoperator '*'. Ansonsten ist es richtig.
 
M

Moemanyy

Mitglied
@httpdigest die lösung ist von der Laufzeit ja nicht so schön. Wie wäre dein Ansatz dafür ?
Wir sind ja hier in einer exponentiell Lösung, könnte man das auch Linear hinbekommen ?

Vielen Dank
mfg
Moemanyyy
 
kneitzel

kneitzel

Top Contributor
Klar geht es linear. Wie würdest du es denn von Hand berechnen?

So sollte man schnell und einfach auf eine lineare Lösung kommen...
 
M

Moemanyy

Mitglied
Okay, ich versuche es mal mit n=5

f(5)= 4*(4*(4*2-1)-2)-4*2-1
f(5)= 97

hab jetzt aber keine Ahnung wie die Rekursionsform dazu aussehen würde.
hmmm

f(n)= ??? // leider keine Ahnung
 
kneitzel

kneitzel

Top Contributor
Hmm, wie gehst du denn genau vor? Du musst meiner Meinung nach lernen, da Handlungswege für Dich zu finden und es Dir bewusst zu machen, was du machst .,.

Hier bedeutet das, dass du dir die Serie aufschreibst:
1: 1
2: 2
3: 4*2 - 1 = 7
4: 4*7 - 2 = 26
5: 4*26 - 7 = 97
...

So kann man das berechnen von Hand ... Zeile für Zeile...
Kannst du die Vorgehensweise nachvollziehen?

was brauchst du für eine Zeile? Das was du brauchst, sind dann die Parameter ...
Was habe ich für die Zeile 5:.... gebraucht?
 
MoxxiManagarm

MoxxiManagarm

Top Contributor
@kneitzel Bist du dir sicher, dass du linear nicht mit iterativ verwechselst? Ich glaube du willst auf einen iterativen Ansatz hinaus, gesucht ist jedoch linear. Ich wäre echt überrascht wenn du hier eine lineare Formel siehst. Ich tue es nicht :oops:

Was ich nur grundsätzlich sagen kann: Die Formel erinnert leicht an Fibonacci und auch hier ist die Herleitung der linearen Formel nicht ganz trivial. https://de.wikipedia.org/wiki/Fibonacci-Folge
 
Zuletzt bearbeitet:
H

httpdigest

Top Contributor
Es geht beides. Iterativ linear sowie rekursiv linear. Man braucht aber eine "Hilfsmethode" (bei rekursiven Funktionen ja nicht unüblich), die nicht die geforderte Signatur int(int) hat, sondern weitere Parameter braucht. Die eigene Funktion int(int) ruft dann nur die eigentliche Hilfsmethode auf.
 
kneitzel

kneitzel

Top Contributor
Öhm, was verstehst ihr unter linearem Algorithmus?

Nach Wikipedia ist dies ein Algorithmus, der in O(n) läuft. Und das tut mein Algorithmus. Unabhängig davon, ob man ihn iterativ oder rekursiv berechnet.
 
kneitzel

kneitzel

Top Contributor
Und ich bin auf Rekursion gegangen vom Wording her(==> Parameter), da ja das etwas gefragt war: "hab jetzt aber keine Ahnung wie die Rekursionsform dazu aussehen würde."

Generell erkennt man aber, dass man nur die zwei vorherigen Werte braucht, um den nächsten Wert zu berechnen. Das hatten wir prinzipiell vor kurzem erst im Tribonacci Thread mit iterativer, rekursiver und Stream Lösung ... und dann sogar einmal Objektorientiert aufgebaut ...
 
MoxxiManagarm

MoxxiManagarm

Top Contributor
Ok, war verwirrt, dachte das ziel wäre eine direkte Formel. Wenn iterativ auch linear heißt, dann passt das.
 
M

Moemanyy

Mitglied
Hey, vielen Dank euch allen.

@kneitzel das mit dem auf schreiben und der Nummerierung hat mir sehr geholfen. Der Satz "Generell erkennt man aber, dass man nur die zwei vorherigen Werte braucht", da hat es "Bing" gemacht bei mir. Vielen Dank nochmal 👍
 
kneitzel

kneitzel

Top Contributor
Ok, war verwirrt, dachte das ziel wäre eine direkte Formel. Wenn iterativ auch linear heißt, dann passt das.
Ein Linearer Algorithmus hat nichts mit iterativ zu tun. Daher mein Link zu Wikipedia:
Ein linearer Algorithmus ist ein Algorithmus dessen Laufzeit linear in der Größe der Eingabe ist. Dies bedeutet, dass der Algorithmus für eine doppelt so große Eingabe in etwa doppelt so lange braucht. Man sagt auch: "Der Algorithmus ist in O(n)".
Und hier sind lineare Algorithmen möglich - egal ob iterativ oder rekursiv.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
A rekursive Listen in Java? Java Basics - Anfänger-Themen 5
G Rekursive Methode mit 2 Aufrufen Java Basics - Anfänger-Themen 1
J Rekursive Folge (a=a-1) Java Basics - Anfänger-Themen 9
G Rekursive Methode liefert augenscheinlich keinen boolean-Wert zurück. Java Basics - Anfänger-Themen 4
veryck Methoden Rekursive Methoden mit Rückgabeparameter Java Basics - Anfänger-Themen 9
macle Rekursive String Methode, Gerade Zahlen rausfiltern Java Basics - Anfänger-Themen 10
M Rekursive Prüfung ob ein Array sortiert ist... Java Basics - Anfänger-Themen 4
J Rekursive swapArray Methode Java Basics - Anfänger-Themen 69
D Rekursive Methode Java Basics - Anfänger-Themen 8
R Methoden rekursive Methoden Java Basics - Anfänger-Themen 6
O Quersumme rekursive Methode Java Basics - Anfänger-Themen 3
B Treetable (rekursive Funktion) aufbauen von Datenbank Java Basics - Anfänger-Themen 4
M Rekursive Methode Programmieren Java Basics - Anfänger-Themen 3
J rekursive Methode Java Basics - Anfänger-Themen 26
M rekursive division/0 mit exception Java Basics - Anfänger-Themen 18
J Rekursive Methode - Ziffern einer Zahl ausgeben Java Basics - Anfänger-Themen 2
M Rekursive Dateiliste erstellen mit Dateiendung(en) ?? Java Basics - Anfänger-Themen 4
S Rekursive Methode Java Basics - Anfänger-Themen 8
O Rekursive Methode Java Basics - Anfänger-Themen 4
V Methoden Rekursive Methode mit String als Rückgabe Java Basics - Anfänger-Themen 7
K Rekursive Methode Java Basics - Anfänger-Themen 1
K Rekursive Methode für Fakultät mit BigInteger Java Basics - Anfänger-Themen 10
L Rekursive Methode a * b berechnen Java Basics - Anfänger-Themen 2
L Rekursive Methode zur Berechnung der Potenz q hoch p Java Basics - Anfänger-Themen 17
J Methoden Rekursive Return Methode Java Basics - Anfänger-Themen 2
G Harmonische Rekursive Folge Java Basics - Anfänger-Themen 3
T Stack Overflow - Rekursive Fibonacci Java Basics - Anfänger-Themen 10
B Datentypen Suchbaum - Rekursive Ausgabe Java Basics - Anfänger-Themen 1
P Methoden Rekursive Methode für Potenzen Java Basics - Anfänger-Themen 2
M Methoden Binäre Suche als rekursive Variante Java Basics - Anfänger-Themen 5
B Rekursive Algorithmus schreiben Java Basics - Anfänger-Themen 8
S Eine rekursive Lösung Java Basics - Anfänger-Themen 4
S Int zu Hexadezimal - Rekursive Methode Java Basics - Anfänger-Themen 2
M Rekursive Suche in einem Feld Java Basics - Anfänger-Themen 11
N Rekursive Addition mit Scanner Java Basics - Anfänger-Themen 12
shiroX OOP Rekursive und Iterative Definition Java Basics - Anfänger-Themen 2
B Methoden Rekursive Methoden Java Basics - Anfänger-Themen 2
T Iterative Pi Berechnung in Rekursive Java Basics - Anfänger-Themen 2
C rekursive methode Java Basics - Anfänger-Themen 2
D Methoden Rekursive Methoden Java Basics - Anfänger-Themen 13
R rekursive Methode funktioniert nicht Java Basics - Anfänger-Themen 4
M Stürzen alle Rekursive Methoden irgendwann ab? Java Basics - Anfänger-Themen 11
D Primzahlen und Rekursive Liste Java Basics - Anfänger-Themen 29
R Rekursive Methode, Files finden Java Basics - Anfänger-Themen 2
S rekursive folge verbessern Java Basics - Anfänger-Themen 2
C rekursive Methode verstehe nicht! Java Basics - Anfänger-Themen 3
S Methoden rekursive Methode funktioniert nicht Java Basics - Anfänger-Themen 4
E Rekursive Methode Java Basics - Anfänger-Themen 3
N Methoden Rekursive Fibonaccizahlen mit Array Java Basics - Anfänger-Themen 2
R Rekursive Ausgabe eines Binärbaums Java Basics - Anfänger-Themen 4
J Methoden Rekursive Potenz ohne Math.Pow() Java Basics - Anfänger-Themen 9
A Rekursive Methode in Iterative umwandeln Java Basics - Anfänger-Themen 6
S Labyrith Rekursive Wegsuche Java Basics - Anfänger-Themen 4
C Rekursive Methode - Ziffern in Zahl Java Basics - Anfänger-Themen 33
U Dezimal zu Hexadezimal rekursive Funktion Java Basics - Anfänger-Themen 8
M rekursive Funktion zur Berechnung der Spiegelzahl Java Basics - Anfänger-Themen 7
L iterative und rekursive Folge Java Basics - Anfänger-Themen 20
G Rekursive Methode Java Basics - Anfänger-Themen 3
B OOP Einfach verkettete Liste - rekursive Methoden Java Basics - Anfänger-Themen 1
E Rekursive Methode mit Zufallsarray Java Basics - Anfänger-Themen 6
E Rekursive Methode Java Basics - Anfänger-Themen 18
U Rekursive lösung von pascal dreieck Java Basics - Anfänger-Themen 11
M Rekursive Methode - wo ist der Fehler? Java Basics - Anfänger-Themen 4
J rekursive methode Java Basics - Anfänger-Themen 6
H ScrollBar inaktiv / Rekursive Methode Java Basics - Anfänger-Themen 4
J Rekursive Methode Java Basics - Anfänger-Themen 11
G Rekursive Methode Java Basics - Anfänger-Themen 5
N Rekursive Berechnung der Höhe eines binären Baumes Java Basics - Anfänger-Themen 4
K Rekursive Methoden Java Basics - Anfänger-Themen 15
K Rekursive Funktion (Verständnissfrage) Java Basics - Anfänger-Themen 5
S Rekursive Bruch potenzierung Java Basics - Anfänger-Themen 2
D rekursive Summenberechnung Java Basics - Anfänger-Themen 8
J Rekursive Methode: Fakultaet berechnen Java Basics - Anfänger-Themen 5
E Rekursive definierten Folge Java Basics - Anfänger-Themen 10
A HILFE! Rekursive Funktion Java Basics - Anfänger-Themen 20
kulturfenster rekursive Binaere Suche Java Basics - Anfänger-Themen 12
F Rekursive Aufrufe, Parameterübergabe, call by reference Java Basics - Anfänger-Themen 3
G Rekursive Berechnung von n über k schlägt fehl Java Basics - Anfänger-Themen 5
B Rekursive & schreiben im ArrayList Java Basics - Anfänger-Themen 2
J Rekursive Fkt. Java Basics - Anfänger-Themen 2
A Rekursive Dateisuche Java Basics - Anfänger-Themen 12
K rekursive Funktion mit mehreren Parametern Java Basics - Anfänger-Themen 5
G rekursive Methode Java Basics - Anfänger-Themen 3
N rekursive Beispiele Java Basics - Anfänger-Themen 3
G rekursive u iterative Methode Java Basics - Anfänger-Themen 8
G Rekursive Methode Java Basics - Anfänger-Themen 7
ven000m Rekursive Funktionen - Frage Java Basics - Anfänger-Themen 16
D rekursive ausgabe einer zahl Java Basics - Anfänger-Themen 14
S Rekursive Funktionen in imperative Funktionen umwandeln Java Basics - Anfänger-Themen 2
M Rekursive Binärsuche Java Basics - Anfänger-Themen 6
S rekursive methoden Java Basics - Anfänger-Themen 5
M Packages erstellen mit Java-Editor Java Basics - Anfänger-Themen 6
mr.kottig Großeltern herausfinden Java - Map? Java Basics - Anfänger-Themen 16
L Java erstellt leere Datei Java Basics - Anfänger-Themen 8
D Java Übungsaufgaben Java Basics - Anfänger-Themen 6
A Standardabweichung in Java berechnen Java Basics - Anfänger-Themen 10
H Java fx Java Basics - Anfänger-Themen 3
J JAVA-Problem blockiert MEDIATHEKVIEW Java Basics - Anfänger-Themen 13
M Java Anfang Java Basics - Anfänger-Themen 13
D Java Thread wartet nur ein mal Java Basics - Anfänger-Themen 1

Ähnliche Java Themen

Anzeige

Neue Themen


Oben