Problem mir Rekursion

sasch00

Hallo!

Ich hab ein kleines Problem mit dem Verständnis, der Rekursion

Ich soll das allbekannte Mergesort in rekursiver Form schreiben, doch verstehe ich den Rekursiven aufrauf nicht.
Wenn ich inerhalb des Unterprogramms, das Unterprogramm erneut aufrufe, wird dann alles erneut ausgeführt oder alles ab dem erneuten Aufruf oder wie muss ich das verstehen?

Vielen dank im voraus

c.rackwitz

zur rekursion nehm ich mal das beispiel fakultät

5! = 1 * 2 * 3 * 4 * 5
n! = 1 * 2 * ... * (n-1) * n

also würde man fak(5) aufrufen.

int fak(int n)
{
    if (n <= 1) return 1;
    return n * fak(n-1);
}

wenn ich fak(5) aufrufe, würde ich "5 * fak(4)" zurückbekommen.
wenn ich fak(4) aufrufe, würde ich "4 * fak(3)" zurückbekommen.
wenn ich fak(3) aufrufe, würde ich "3 * fak(2)" zurückbekommen.
wenn ich fak(2) aufrufe, würde ich "2 * fak(1)" zurückbekommen.
wenn ich fak(1) aufrufe, würde ich "1" zurückbekommen. jetzt hat das if gegriffen. kein "1 * fak(0)" oder "0 * fak(-1)"

das würde zu dem werden: "5*4*3*2*1"

bei rekursion ist immer zu beachten, dass irgendwann mal nicht rekursiert wird. (deswegen das if, als abbruchbedingung).

sasch00

Danke für die schnelle Antwort
Das hilft mir schon ein ganze stück weiter.

Caipi

Hallo, vielleicht noch ein grafischer Ablauf wenn n = 5

fak(5)
  |-----> return 5 * fak(4)
                     |------> return 4 * fak(3)
                                          |------> return 3 * fak(2)                                                                                                                                                                    
                                                               |----------> return 2 * fak(1)
                                                                                          |-------> return 1;

Caipi

sasch00

Kann ich auch einzelne Programmteile aus der Rekursion ausschließen oder muss dafür ein neues Unterprogramm geschrieben werden?

sasch00

ich hoffe, dass ich mich verständlich ausgedrückt habe.

Hier nochmal mein Problem konkretisiert.

void mergesort (int n, int a[], int work [])
{
   int i, j, j1, j2, k, links, rechts, temp;
   j = 0;
   mergesort(n , a, work);
   if (j <= 4)
   {
      if (a[n-j] < a[n-(j+1)])
      {
          temp = a[n-(j+1)];
          a[n-(j+1)] = a[n-j];
          a[n-j] = temp;
          j = j + 1;
       }
   }

Das j = 0; möchte ich nicht jedesmal wieder auf 0 gesetzt bekommen, doch wie realiesiere ich das?

Vielen Dank im voraus

c.rackwitz

nein, dein code ist unsinn.
die funktion ruft sich selber bei dir ja mit den gleichen werten auf, was nicht sein darf.

sinn der rekursion ist es, ein großes problem in kleinere aufzuteilen.
die funktion hat nun die aufgabe, das problem zu teilen, sich selbst mit einem kleineren problem aufzurufen und selber den restlichen teil des problems zu lösen.

sasch00

achso, ich dachte er zählt dabei auch runter.
Allerding, wo ich so darüber nachdenke, woher soll es wissen, was es dekrementieren soll.
Aber wird dann alles wiederholt oder nur der Teil, der nach dem erneuten Aufruf kommt?

sasch00

Ich glaube meine Frage hat sich erledigt,
wenn ich das jetzt richtig verstanden habe, wiederholt er das ganze Programm mit dem erneuten Aufruf.

Danke für die schnellen hilfen