Rekursive Funktionen - Frage

[ven000m]

Hallo,

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

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?

 

[Beni]

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]

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:

 

[Nova]

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]

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

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.

 

[Nova]

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:

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]

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]

Hallo,

noch eine andere Aufgabe:

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

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?

 

[Nova]

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

 

[SnooP]

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]

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?

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]

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

 

[SnooP]

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!

 

[ven000m]

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

Das ist sehr gut, so versteht man das auch richtig gut. :applaus:

 

[Nova]

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]

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]

das ist der "geniale" schritt

genau wie beim erraten der fortsetzung einer zahlenfolge

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