Rekursion: Wert eines Aufrufes

raz0light

raz0light

Grünschnabel
Sehr geehrte Damen und Herren,

Ich habe ein Verständnisproblem. Ich muss für die Uni/Prüfung lernen, wie man den Wert eines rekursiven Aufrufes einer Methode ausrechnet. (Ist das verständlich?)

KZ4w0hv.png


Wie man die Reihenfolge und die Parameter hinbekommt, habe ich verstanden, aber nicht, was für ein Wert da raus kommt. Da ist doch überhaupt keine Formel, die man überhaupt berechnen könnte, oder bin ich zu blöd? :D
Der Hiwi, mit dem Ich gesprochen hat, hat das auch nicht wirklich erklärt, sondern nur mit den Augen gerollt und wahrscheinlich gedacht, was für ein Idiot ich doch sei..

Gruß
raz0light
 
Moin,

nimm' Dir einfach Papier und Stift und mach' es händisch!

Erster Aufruf f(6,4):
- x und y ungleich 0, also in den else-Fall und dort x und y ersetzen: f(4,4) - (3 * f(2,6%4)) // da Punkt VOR Strichrechnung
- so, jetzt das Gleiche jetzt für f(4,4) solange bis x oder y gleich 0 ist ==> jetzt hast du das erste Ergebnis !
- danach das für '3 * f(2,6%4)' ==> irgendwann hast Du das zweite Ergebnis !
- usw.
- jetzt noch voneinander anziehen --> FERTIG :)

Gruß Klaus
 
Weils grad so lustig ist und ich auf einen Upload warten muss...

Code: 
f(x=6,y=4)
	x ist nicht 0, also nicht Ergebnis 2
	y ist auch nicht 0, also nicht Ergebnis 1
	f(x-2,y) also f(x=4,y=4)
		x ist nicht 0, also nicht Ergebnis 2
		y ist auch nicht 0, also nicht Ergebnis 1
		f(x-2,y) also f(x=2,y=4)
			x ist nicht 0, also nicht Ergebnis 2
			y ist auch nicht 0, also nicht Ergebnis 1
			f(x-2,y) also f(x=0,y=4)
				x ist 0, also Ergebnis "2"
			f(y-2,x%4) also f(x=2,y=2)
				x ist nicht 0, also nicht Ergebnis 2
				y ist auch nicht 0, also nicht Ergebnis 1
				f(x-2,y) also f(x=0,y=2)
					x ist 0, also Ergebnis "2"
				f(y-2,x%4) also f(x=0,y=2)
					x ist 0, also Ergebnis "2"
				f(x-2,y)-3*f(y-2,x%4) ist damit "-4"
			f(x-2,y)-3*f(y-2,x%4) ist damit "14"
		f(y-2,x%4) also f(x=2,y=0)
			y ist 0, also Ergebnis "1"
		f(x-2,y)-3*f(y-2,x%4) ist damit "11"
	f(y-2,x%4) also f(x=2,y=2)
		x ist nicht 0, also nicht Ergebnis 2
		y ist auch nicht 0, also nicht Ergebnis 1
		f(x-2,y) also f(x=0,y=2)
			x ist 0, also Ergebnis "2"
		f(y-2,x%4) also f(x=0,y=2)
			x ist 0, also Ergebnis "2"
		f(x-2,y)-3*f(y-2,x%4) ist damit "-4"
	f(x-2,y)-3*f(y-2,x%4) ist damit "23"

Max. Tiefe 5 (wenn der äußerste Aufruf 1 und nicht 0 ist)

Nein, es terminiert nicht immer für positive x und y. zB. x=1, y=1. Beide nicht 0, daher kommt das erste f(x-2,y), also f(-1,1). Beide nicht 0, f(x-2,y) ist f(-3,1). Nächstes Level f(-5,1). Usw. bis zum Overflow. Kurz, x muss gerade sein. Und Weil es beim anderen Teil auch y-2 gibt muss y auch gerade sein.
 
Zuletzt bearbeitet:
Moin sheel,

ich frage mich gerade, ob das stimmt ...
Wenn Du in der zwölften Zeile ( f(y-2,x%4) also f(x=2,y=2) ) in den zweiten Ausdruck gehst, müsste doch 'x' immer noch 6 und 'y' immer noch 4 sein, oder nicht?
Beide Werte werden doch innerhalb nicht geändert ....
Oder steh' ICH jetzt auf dem Schlauch??

Gruß Klaus
 
oops, ja, your alright ;)
Aber Zeile 24? Das ist doch dann wieder Level 1, oder ?

EDIT:
aber '23' ist richtig, habe es gerade mal ausprobiert!
Muss mal im Debugger schauen, wo mein Denkfehler ist ...

Gruß Klaus
 
Zuletzt bearbeitet:
Btw., eine Funktion in O(1) (ja, muss noch immer warten...)
C++: 
int f(int x, int y)
{
	if(x < 0 || y < 0 || x % 2 || y % 2) return 0;
	if(x == 0) return 2;
	if(y == 0) return 1;
	int res = 2 + (-3) * x;
	y -= 2;
	if(y)
	{
		res += (((x + 2) >> 1) * 3 + (x >> 2)) * 3;
		y -= 2;
	}
	if(y) res += y * ((x + 1) >> 2) * 9;
	return res;
}
(Achtung mit den Shifts: Nicht irgendwie zusammenfassen oder so; das richtige Ergebnis hängt davon ab dass da Kommastellen wegfallen)

x muss gerade und >= 0 sein, y auch
0,0 => 2
0,? => 2
?,0 => 1
f(x,2) => 2+(-6)*(x/2)
f(x,4) => 2+(-6)*(x/2) + (((x+2)-(x+2)%4)/4)*18 + ((x-x%4)/4)*3
f(x,4+z) => 2+(-6)*(x/2) + (((x+2)-(x+2)%4)/4)*18 + ((x-x%4)/4)*3 + ((z-4)/2)*(x + x%4)*18/4
 
Zuletzt bearbeitet:
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück