Rekursive Funktionen - Frage

Status
Nicht offen für weitere Antworten.
ven000m

ven000m

Bekanntes Mitglied
Hallo,

ich habe eine Aufgabe vor mir und kann mir nicht genau das Ergebnis erklären:

Code:
public static int f(int x, int y)
{if(y==0) return x; else return g(x-1,y);}

public static int g(int x, int y)
{if(y==0) return x; else return f(x,y-1);}

Die Fragestellung lautet: "Welche mathematische Funktion f(x,y) in Abhängigkeit von x und y wird hier berechnet?."

Das Ergebnis lautet: x-1y

Zielt nun die Fragestellung mit f(x,y) einzig auf die erste Funktion ab, oder ist damit das mathematisch allg. f(x) gemeint und hat keinen Bezug zur ersten Funktion? Brauche ich mir je nachdem was genannt wird (ob f(x,y) oder g(x,y) nur die jeweilige Funktion ansehen?
 
B

Beni

Gast
Eine Funktion (im Mathematischen Sinne) kann beliebig viele Argumente haben. So wie ich das verstanden habe, kannst du "die mathematische Funktion f( x, y )" gleichsetzen mit "was berechnet die java-Methode int f( int x, int y )?".
 
ven000m

ven000m

Bekanntes Mitglied
Die Fragestellung lautet: "Welche mathematische Funktion f(x,y) in Abhängigkeit von x und y wird hier berechnet?."

Nun, die Frage stelle ich mir auch. Laut Fragestellung ist ja die obere Funktion gefragt oder?

Ich meine diese berechnet ja f(x,y) in Abhängigkeit von x und y. Das Ergebnis ist ja das Return Argument?

Ist hier jemand der sich damit auskennt? :roll:
 
N

Nova

Bekanntes Mitglied
Hallo,

Ich würde sagen g(x,y) ist nur eine "Hilfsmethode", gefragt ist was rauskommt wenn man die Funktion f mit 2 Werten x und y aufruft, das die Funktion f noch eine Hilfsfunktion aufruft ist uninteressant.
Ist sowas wie f(x)=g(x)+x² wobei g(x) = x²+1
=> f(x) = 2x²+1 ist die Lösung

rauskommen tut (wenn ich mich nicht völlig vertan habe) f(x,y) = x-y
Denn wenn y != null ist wird die Methode g mit g(x-1,y) aufgerufen, diese reduziert y um 1 =>dasselbe als würde gleich f(x-1,y-1) aufgerufen.
Das mit dem "if(y==0)" dient nur zur Verwirrung, in g kann y niemals 0 sein! Denn die Funktion g wird ja nur aufgerufen gerade wenn y ungleich 0 ist!


mfg
Christian
 
ven000m

ven000m

Bekanntes Mitglied
Hallo,

danke Christian, ja du hast Recht.

So stimmt auch die Lösung, die Erklärung ist gut, aber wie soll man jetzt auf eine modifizierte Variante von selber kommen?

z.B.:
Code:
public static int f(int x, int y) 
{if(y==0) return x; else return g(4x-15,y);} 

public static int g(int x, int y) 
{if(y==0) return x; else return f(x,y-1);}

Wäre hier die Lösung: 4x-15y?

Dann habe ich es verstanden.
 
N

Nova

Bekanntes Mitglied
Hallo,

y wird jedesmal um eins verkleinert bis y = 0 ist.
D.h. es wird 15 mal g(4x-15,y) aufgerufen.
=> f verändert x auf 4x-15 (=> nur x wird verändert)
=> g senkt y um 1 (=> nur y wird verändert)

Wenn man sich das betrachtet sieht man das genau y mal f(4x-15,y) ausgerechnet wird, dann ist nämlich y = 0.
Also einfach anschauen
WAS passiert bei jedem Durchlauf? (Hier: x wird zu 4x-15, y wird um eins verringert)
WIE OFT wird die Funktion aufgerufen (Hier: y mal)
WAS wird zurückgegeben (Hier einfach nur x)

=> Ergebnis: f(x,y) = y*(4x-15)


Übrigens: Die beiden Aufgabenstellungen funktionieren natürlich nur wenn man positive Zahlen für y einsetzt, sonst kann y nämlich niemals 0 erreichen weil es ja immer ums eins verringert wird...



Man kann den Code auch umschriben, dann wird es einfacher:
Code:
public static int f(int x, int y){
    if (y == 0){
        return x;
    } else {
        f(4x-15,y-1);
    }
}

Das ist immer noch rekursiv, nur die Methode g wurde entfernt.


mfg
Christian[/code]
 
ven000m

ven000m

Bekanntes Mitglied
Danke...


dann lag ich mit meiner Lösung ja gar nicht soo falsch.

Also hilft wirklich nur durchgehen? Weil das Ergebnis was ich für richtig hilt steht ja direkt in f(x,y)->> 4x-15y.
 
ven000m

ven000m

Bekanntes Mitglied
Hallo,

noch eine andere Aufgabe:

Welche mathematische Funktion f(x,y) in Abhängigkeit von x und y wird hier berechnet?


Code:
public static int f(int x, int y) 
{if(y==0) return x; else return g(x+2,y);} 

public static int g(int x, int y) 
{if(y==0) return x; else return f(x,y-1);}

In der Lösung steht z.B. als erster Satz:
Die Funktion f(x,y) berechnet den Ausdruck g(x+2,y). Danach folgen einige Erklärungen und als Abschluss:
..und am Schluss als Ergebnis des Gesamtaufrufs geliefert, das somit genau dem Wert x+2y entspricht.

Ist jetzt mit dem ersten Satz die Fragestellung bereits beantwortet? Wenn ja, wieso heißt es g(x+2,y) das wäre ja aus der Funktion f(x,y) lediglich abgeschrieben?

Oder ist der Schluss x+2y die Antwort der eigentlichen Aufgabe, worauf zielt die Fragestellung nun genau ab?
 
N

Nova

Bekanntes Mitglied
Hallo,

Also das f(x,y) den Ausdruck g(x+2,y) berechnet ist FALSCH!
Es hängt nämlich von y ab ob x oder g(x+2,y) zurückgeliefert wird.
Somit kannst du also gar nicht direkt sagen was zurückgeliefert wird wenn du y nicht kennst!

Und g(x+2,y) ist ncht die Lösung, sondern nur ein anderer Ausdruck/eine andere Funktion (und diese ruft ja wieder die Funktion f auf), sondern x+2y.


mfg
Christian
 
S

SnooP

Top Contributor
Nunja... die Funktion gibt bei y==0 ebenfalls lediglich x zurück -genauso wie f - demnach unterscheiden sich die beiden Funktionen im Fall y==0 nicht. Wenn y!=0 dann ist f == g(x+2, y)

soo - mal eingesetzt könnte man sagen: g(x+2, y-1)... d.h. auf dem alten wert von x wird y-mal 2 dazuaddiert. Letztlich kommt man also mit dieser Rückwärtszählüberlegung, dass die Kreuzrekursion mit den Funktionen f und g zu der rekursionsfreien Funktion h(x,y) = x+2y verkommt ;)

man erkennt auch, dass es direkt an y liegt wie oft zwei dazuaddiert wird... also 2*y ... der anfangswert von x wird hingegen nie geändert. Daher kann es auch nicht sowas wie (x+2)y sein.
 
ven000m

ven000m

Bekanntes Mitglied
Code:
g(x+2, y-1)

Mhm einige von Euch setzen die beiden Funktionen immer zusammen. Das scheint mir die richtige Methode zu sein, wie komme ich dann zum Ausgabe Ergebnis, kann ich das nur durch ausprobieren hinkriegen oder gibt es da eine Art Regelmäßigkeit/Trick - worauf ich dann schnell komme?

Code:
public static int f(int x, int y) 
{if(y==0) return x; else return g(x+2,y);} 

public static int g(int x, int y) 
{if(y==0) return x; else return f(x,y-1);}

Bis jetzt war ja immer der Rückgabewert der 1. Funktion auch das Ergebnis hier x+2y - ist das jetzt reiner Zufall?
Bei meinem Anfangspost war es ja x-y bzw. in der Funktion f(x,y) war der Rückgabewert x-1y was ja das gleiche ist.
 
Bleiglanz

Bleiglanz

Gesperrter Benutzer
wohl kein Zufall

lös doch einfach mal die ganz allgemeine aufgabe

f(x,y) = g(x+a,y) = f(x+a,y-1) = ... = f(x+ay,0) = x+ay

also für a=-1 und a=+2 deine zwei aufgaben gelöst

die Antwort bei f(x,y) = f(4x+15,y-1) ist komplizierter als oben angegeben
 
S

SnooP

Top Contributor
Im Prinzip hast du's da häufig mit mathematischen Reihen oder Folgen zu tun... eine entsprechende Funktion daraus zu erlesen ist nicht immer so einfach. Bei späteren schwierigeren Aufgaben empfiehlt es sich ein entsprechendes Mathe-Kompendium zu haben in dem einige Standard-Reihen beschrieben werden (Taylorreihe, Geometrische,...) - das allerdings wirklich nur, wenn man es mit bloßem hinsehen nicht sieht ;) ... ansonsten muss man halt einfach denken, was da eigentlich passiert bei der jeweiligen Rekursion. Das ist im Wesentlichen Übungssache.
Einsetzen bringt auf jedenfall schonmal weiter ;) ... vor allem sollte man genau gucken welche der Variablen die der Rekursion mitgegeben werden denn tatsächlich die Berechnung enthält und welche offenbar lediglich zum Abbruch der Funktion führt. Das kann allerdings bei manchen Rekursionen auch sehr viel komplexer sein... von daher - kein wirkliches Patentrezept!
 
N

Nova

Bekanntes Mitglied
SnooP hat gesagt.:
Nunja... die Funktion gibt bei y==0 ebenfalls lediglich x zurück -genauso wie f - demnach unterscheiden sich die beiden Funktionen im Fall y==0 nicht. Wenn y!=0 dann ist f == g(x+2, y)

soo - mal eingesetzt könnte man sagen: g(x+2, y-1)... d.h. auf dem alten wert von x wird y-mal 2 dazuaddiert. Letztlich kommt man also mit dieser Rückwärtszählüberlegung, dass die Kreuzrekursion mit den Funktionen f und g zu der rekursionsfreien Funktion h(x,y) = x+2y verkommt ;)

man erkennt auch, dass es direkt an y liegt wie oft zwei dazuaddiert wird... also 2*y ... der anfangswert von x wird hingegen nie geändert. Daher kann es auch nicht sowas wie (x+2)y sein.

Hallo,

g(x+2,y) liefert im Fall y == 0 x+2 zurück! (denn der x-Wert für die Funktion ist ja (x+2))
Sei z.B. x = 3 und y= 0, g(x+2,y)=g(5,0) liefert 5 zurück!


mfg
Christian
 
ven000m

ven000m

Bekanntes Mitglied
f(x+a,y-1) = ... = f(x+ay,0)

Die Punkte (...) stellen wohl die Zählschritte dar. Aber wieso steht das y erst rechts vom Komma, danach plötzlich links? Wenn ich denke y=2 und danach y=2-1 > 1 und dann y=1-1 > 0 dann müsste dort doch stehen f(x+a,0) oder so wieso denn dann ay . Das du die Funktion zusammensetzt ist mir einleuchtend aber ich verstehe noch nicht ganz wie von ... auf das Ende kommst und dann es plötzlich heißt x+ay,0 wenn doch 0 für y stehen müsste.
 
Bleiglanz

Bleiglanz

Gesperrter Benutzer
das ist der "geniale" schritt

genau wie beim erraten der fortsetzung einer zahlenfolge

Code:
f(x+   a,y-1)
f(x+2*a,y-2)
f(x+3*a,y-3)

hmm, mal schauen, beim n.ten schritt würde das also so aussehen

f(x+n*a, y-n)

hoppla, wenn n = y ist, also wenn ich das ganze "y-mal" mache

f(x+y*a, y-y) = f(x+a*y,0)

das y wandert also "in 1er schritten" von rechts nach links :)
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
S Rekursive Funktionen in imperative Funktionen umwandeln Java Basics - Anfänger-Themen 2
M Rekursive Java-Methode Java Basics - Anfänger-Themen 13
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
A rekursive Listen in Java? Java Basics - Anfänger-Themen 5
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
D rekursive ausgabe einer zahl Java Basics - Anfänger-Themen 14
M Rekursive Binärsuche Java Basics - Anfänger-Themen 6
S rekursive methoden Java Basics - Anfänger-Themen 5
A Variablen Definitionen zu Codes und Funktionen. Java Basics - Anfänger-Themen 3
Z If Funktionen, GUI, Fachklasse Java Basics - Anfänger-Themen 25
H Frage zu Methoden/Funktionen Java Basics - Anfänger-Themen 3
M Vererbung Funktionen in Basisklasse deklarieren Java Basics - Anfänger-Themen 4
J Funktionen auf der Rückgabe eines Stacks (pop) Java Basics - Anfänger-Themen 6
J Funktionen Java Basics - Anfänger-Themen 9
S Klassen Class mit Funktionen importieren Java Basics - Anfänger-Themen 1
B Funktionen von außen aufrufen Java Basics - Anfänger-Themen 1
M Klassen Funktionen aus anderen Klassen benutzen Java Basics - Anfänger-Themen 3
G funktionen der super-klasse von der super-klasse Java Basics - Anfänger-Themen 6
R Funktionen Synchron laufen lassen Java Basics - Anfänger-Themen 10

Ähnliche Java Themen

Anzeige

Neue Themen


Oben