Rekursion (anhand von Mergesort) nachvollziehen

[ApexPredator]

Nachdem ich nun schon oft genug mal hier rein gestöbert habe, bin nun ich es, der eine Frage hat.
Und zwar geht es um das Thema Rekursion.
Ich dachte, ich hätte es verstanden, doch nun kann ich diesen Code(Merge Sort Algorithmus) nicht nachvollziehen, wie die Rekursion hier funktioniert.
Hier der Code(funktioniert tadelos):

public static void merge_sortierung(int A[],int p, int r){
		int q;
		if(p<r){
			q=(p+r)/2;
			merge_sortierung(A,p,q);
			merge_sortierung(A,q+1,r);
			merge(A,p,q,r);
		}
	}
	public static void merge(int A[],int p, int q, int r){
		int B[]=A.clone();
		int i,j,k;
		i=p;
		j=q+1;
		k=p;
		while(i<=q && j<=r){
			if(B[i]<=B[j]) A[k++]=B[i++];
			else A[k++]=B[j++]; 	}
		while(i<=q) A[k++]=B[i++];
		B=null;
		}
	}

Kann mir hier jemand erklären, wie der rekursive Aufruf nun denn genau funktioniert? Rekursion bedeutet doch, die Methode(z.B. "merge_sortierung") innerhalb der Methode erneut aufzurufen. Verstehe aber ehrlich gesagt nicht, wieso die Methode funktioniert...springt der Compiler im Prinzip beim Aufruf der rek. Methode nicht immer wieder an den Anfang, sodass der Code drunter nicht ausgeführt wird?

Bedanke mich für jede Hilfe

 

[QuintusVarus]

Bei der Rekursion ist es praktisch so, als würdest du innerhalb deiner Methode eine andere Methode aufrufen, nur dass du hier eben speziell die gleiche Methode aufrufst (meist mit anderen Argumenten). Nachdem die aufgerufene Methode also durchgelaufen ist, kehrst du wieder zurück zur aufrufenden Methode. Hier wird dann einfach der nächste Befehl ausgeführt. Es ist halt durch die Verschachtelung von Aufrufen nicht leicht, sich vorzustellen was passiert.

In deinem Beispiel würde es mit einem Array mit 6 Elementen so aussehen:

Als erstes wird merge_sortierung(array, 0, 5) aufgerufen, darin wird dann, quasi als Subroutine, merge_sortierung(array, 0, 2) aufgerufen. Diese wiederum ruft merge_sortierung(array, 0, 1) auf, welches seinerseits wieder merge_sortierung(array, 0, 0) aufruft. Da hierdrin jetzt aber die Bedingung "if(p<r)" false ist, wird hier das erste mal nicht verschachtelt, sondern der nächste Befehl in merge_sortierung(array, 0, 1) ausgeführt und der ist merge_sortierung(array, 1, 0). Hier ist dieselbe Bedingung false und es folgt ein Aufruf von merge(0, 0, 0). Wenn er dann damit fertig ist, kehrt er zurück zum nächsten Befehl in merge_sortierung(array, 0, 2) und der wäre dann merge_sortierung(array, 3, 5). Dort frist er sich wieder rekursiv in die Tiefe, bis er wieder zurückkehrt und merge aufruft usw.

Ich hoffe, ich konnte die Idee rüberbringen und habe dich nicht durcheinander gebracht

 

[ApexPredator]

Danke schon mal hierfür, mit dieser Erklärung kann ich schon mal was anfangen
Heißt also, wenn die if-Schleife false ist, springt der Compiler nun zur nächsten Stelle (also der 2. merge_sortierung Auruf) etc. ?

 

[stg]

wenn die if-Schleife false ist, springt der Compiler nun zur nächsten Stelle

Dieser Satz enthält so viele Fehler, dass man gar nicht weiß, wo man anfangen soll ....
:-O
Zunächst einmal: if-schleife.de
Dann: Eine if-Abfrage kann nicht wahr oder falsch sein, sondern nur die Bedingung, anhand derer entschieden wird, ob der anschließende Code-Block ausgeführt wird, oder nicht.
Der Compiler ist dafür zuständig Programmcode zu kompilieren, sprich er erzeugt aus deinem Programmcode einen für Maschinen lesbaren Code. Während des Programmdurchlaufs spielt der Compiler schon lange nicht mehr mit, seine Arbeit ist längst erledigt...
Aber auch unabhängig davon ist deine Frage nicht verständlich. Wenn welchem if sprichst du hier? Wann soll die zugehörige abgefragte Bedingung falsch sein? Von welcher zweiten merge_sortierung sprichst du hier?

 

[ApexPredator]

My bad, natürlich if-Abfrage, wieso ich das zum 1. Mal schreibe...naja, wie auch immer.
So,meinte natürlich die if-Abfrage in Zeile 3, Mit "zweiter merge_sortierung" Zeile 6.
Habs inzwischen verstanden, Problem gelöst