1. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies. Weitere Informationen

Rekursion: Wert eines Aufrufes

Dieses Thema im Forum "Coders Talk" wurde erstellt von raz0light, 2. März 2017.

  1. 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?)

    [​IMG]

    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
     
  2. vfl_freak

    vfl_freak Premium-User

    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
     
  3. sheel

    sheel I love Asm Administrator

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

    Code (Text):
    1. f(x=6,y=4)
    2.     x ist nicht 0, also nicht Ergebnis 2
    3.     y ist auch nicht 0, also nicht Ergebnis 1
    4.     f(x-2,y) also f(x=4,y=4)
    5.         x ist nicht 0, also nicht Ergebnis 2
    6.         y ist auch nicht 0, also nicht Ergebnis 1
    7.         f(x-2,y) also f(x=2,y=4)
    8.             x ist nicht 0, also nicht Ergebnis 2
    9.             y ist auch nicht 0, also nicht Ergebnis 1
    10.             f(x-2,y) also f(x=0,y=4)
    11.                 x ist 0, also Ergebnis "2"
    12.             f(y-2,x%4) also f(x=2,y=2)
    13.                 x ist nicht 0, also nicht Ergebnis 2
    14.                 y ist auch nicht 0, also nicht Ergebnis 1
    15.                 f(x-2,y) also f(x=0,y=2)
    16.                     x ist 0, also Ergebnis "2"
    17.                 f(y-2,x%4) also f(x=0,y=2)
    18.                     x ist 0, also Ergebnis "2"
    19.                 f(x-2,y)-3*f(y-2,x%4) ist damit "-4"
    20.             f(x-2,y)-3*f(y-2,x%4) ist damit "14"
    21.         f(y-2,x%4) also f(x=2,y=0)
    22.             y ist 0, also Ergebnis "1"
    23.         f(x-2,y)-3*f(y-2,x%4) ist damit "11"
    24.     f(y-2,x%4) also f(x=2,y=2)
    25.         x ist nicht 0, also nicht Ergebnis 2
    26.         y ist auch nicht 0, also nicht Ergebnis 1
    27.         f(x-2,y) also f(x=0,y=2)
    28.             x ist 0, also Ergebnis "2"
    29.         f(y-2,x%4) also f(x=0,y=2)
    30.             x ist 0, also Ergebnis "2"
    31.         f(x-2,y)-3*f(y-2,x%4) ist damit "-4"
    32.     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: 2. März 2017
  4. vfl_freak

    vfl_freak Premium-User

    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
     
  5. sheel

    sheel I love Asm Administrator

    Hm ... warum 6 und 4?
    Zeile 12 ist Level 3, nicht 1.
     
  6. vfl_freak

    vfl_freak Premium-User

    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: 2. März 2017
  7. sheel

    sheel I love Asm Administrator

    Btw., eine Funktion in O(1) (ja, muss noch immer warten...)
    Code (C++):
    1. int f(int x, int y)
    2. {
    3.     if(x < 0 || y < 0 || x % 2 || y % 2) return 0;
    4.     if(x == 0) return 2;
    5.     if(y == 0) return 1;
    6.     int res = 2 + (-3) * x;
    7.     y -= 2;
    8.     if(y)
    9.     {
    10.         res += (((x + 2) >> 1) * 3 + (x >> 2)) * 3;
    11.         y -= 2;
    12.     }
    13.     if(y) res += y * ((x + 1) >> 2) * 9;
    14.     return res;
    15. }
    (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: 2. März 2017
  8. vfl_freak

    vfl_freak Premium-User

    OT:
    Du meine Güte, was compilierst du denn ????
    So groß oder ist der Rechner so langsam ?? :D
    Gruß Klaus
     
  9. sheel

    sheel I love Asm Administrator

    Kein Kompilieren, das Internet ist langsam und die Datenmenge riesig :D
     
  10. vfl_freak

    vfl_freak Premium-User

    achso ... Filme streamen ???
     
Die Seite wird geladen...
Ähnliche Themen - Rekursion Wert eines
  1. bustue
    Antworten:
    21
    Aufrufe:
    723
  2. lostify
    Antworten:
    1
    Aufrufe:
    1.165
  3. Bogat
    Antworten:
    1
    Aufrufe:
    658
  4. Neppo
    Antworten:
    6
    Aufrufe:
    1.400
  5. vogtländer
    Antworten:
    6
    Aufrufe:
    2.143