C++ Rekursionsfunktion / insert item

_fux_

_fux_

0
hi leute,

ich wollte heute mal eine teil-rekursive funktion bauen und war eigntl. auch recht erfolgreich. nur leider passieren seltsame dinge beim ausführen des codes.

es geht um folgendes:
ich programmiere grundlegen erstmal einen einfachen Binärbaum (nur einfügen, löschend und ausgeben) ohne irgendwelche balancing-funktionen (die kommen später).
dafür hatte ich nochmal neu angefangen und mir überlegt, das einfügen teilweise rekursiv zu erledigen, was in dem fall sogar ganz okay ist.
nur leider passiert es, das - wenn ich in der funktion ein return einbaue - noch eine if abfrage ausgeführt wird. diese wird zuwar nicht ausgeführt, aber trotzdem verändert er das return, heißt gibt etwas falsches zurück und werte werden überschrieben.

wer mir helfen will:
ich habe screenshots mit code angefügt.
wer lust hat, setzt sich einfach breakpoints an insert und insert_find und schaut sich diese mit F10 an (prozedurschritt).
ich habe schon festvorgegeben werte angelegt, das problem tritt auf, wenn man versucht den wert 47 nach der 8 anzufügen.

im rar-file sind nur bilder und sourcecode (eine header und eine CPP)
 
Wenn ich nichts übersehe:
Code: 
node* tree::insert_find(node *fnode, int wert){ // fängt mit root an und geht hoch und runter
	
	// FALL 1: direkt einfügen, wenn es keine nachfolger gibt / node übergeben, wenn stelle zum einfügen gefunden
	if(fnode->left == nullnode && fnode->right == nullnode){
			return fnode; 
	}

	// FALL 2: richtigen parent finden, wenn es schon nachfolger gibt
	// wenn der einzügendene wert kleiner ist
	if(fnode->data > wert && fnode->left != nullnode){
		fnode = fnode->left;
		insert_find(fnode, wert);
	}

	if(fnode->data < wert && fnode->right != nullnode){
		fnode = fnode->right;
		insert_find(fnode, wert);
	}


	return fnode;
}
wenn Du versuchst 47 einzufügen, sollte so ein Baum im Speicher sein:
Code: 
           5
         .-'-.
      4.'     /99
    .'       /
  3'        8
47 ist größer als 5 - also wird in der zweiten IF Abfrage inser_find aufgerufen. 99 ist größer als 47, also geht es in der ersten IF weiter, 8 passt (zwei nullkinder). Ziel gefunden - return.Jetzt kommt der rekursive Aufstieg: d.h der Code macht nach dem insert_find einfach weiter. Dann kommt der zweite Aufstieg - wieder geht es nach dem inser_find Aufruf weiter. Der gefundene Wert verfällt. Stattdessen gibt der Code pflichtgemäß den aktuellen Knoten zurück. Wenn Du den gefundenen fnode zurückgeben willst, müsste menier Logik nach vor inser_find Aufrufe ein Return hin ;)
Eigentlich müsste das Problem schon früher auftreten.
 
Ok, da war wohl einer schneller. Aber einen tip kann ich dir noch geben. Wenn du den VS-debugger verwendest, ist bei derartigen porblemen der stackviewer ganz nützlich. Du findest ihn unter Debugger->Windows->Callstack (in der deutschen version heißt das ding etwas unglücklich "Aufrufliste")
 
nunja, vor dem aufruf ein return wäre ja nicht so toll :-)

wenn ich den fall teste, also wenn ich 47 einfüge:

(nach einigen aufrufen):

- die fnode ist nun endlich ein pointer auf "8",
- FALL 1 greift:
----> fnode-pointer auf 8 wird mittels return aus Zeile 5 zurückgegeben.

nach zeile 5, springt man prinzipiell aus der funktion insert_find raus, d.h. es wird nichts mehr in dieser funktion ausgeführt.

bei mir passiert nun folgendes im Visual Studio debugger:
ich spring' zu zeile 22 (also zum ende der funktion), als müsste ich nun wieder zur hauptfunktion insert rein kommen.

nun passierts:
danach springt der aber -nicht wie erwartet- in zeile 15 rein.
da aber die 8 kein nachfolger hat, dürfte er nichts verändern.
er springt sogar in zeile 21 rein,. dann wirds komisch.

irgendwie verändert er nun fnode, obwohl das theoretisch gar nicht eingebaut ist, er springt wieder zurück zur 99!
seltsamerweis :(
 
Code: 
return insert_find(fnode, wert);
ein rekursiver Aufruf geht in sich selbst rein. Wenn die Abbfruchbedingung erreicht ist, wird returnt - wie bei einem normalen Funktionsaufruf wird dann mit der nächsten Anweisung weitergemacht. Der Code kann nicht wissen, dass Du eine Rückkehr in die Insert Funktion wünschst ;)
Da der Aufruf aus der Funktion selbst erfolgte, kehrt dieser auch "in sich selbst" zurück. Daher das "unerwartete" Verhalten.
Vielleicht klärt das etwas:
http://www.saar.de/~awa/jrekursion.htm
 
Code: 
return insert_find(fnode, wert)

benutze ich doch gar nicht?!
der link hat mir irgendwie nicht geholfen, also ich versteh' das nicht so ganz =D

deine erklärung war da viel verständlicher,
trotzdem ists ja irgendwie.... seltsam Oo
 
Code: 
node* tree::insert_find(node *fnode, int wert){ // fängt mit root an und geht hoch und runter
	
	// FALL 1: direkt einfügen, wenn es keine nachfolger gibt / node übergeben, wenn stelle zum einfügen gefunden
	if(fnode->left == nullnode && fnode->right == nullnode){
			return fnode; 
	}

	// FALL 2: richtigen parent finden, wenn es schon nachfolger gibt
	// wenn der einzügendene wert kleiner ist
	if(fnode->data > wert && fnode->left != nullnode){
		fnode = fnode->left;
		return insert_find(fnode, wert);
	}

	if(fnode->data < wert && fnode->right != nullnode){
		fnode = fnode->right;
		return insert_find(fnode, wert);
	}


	return fnode;
}
also den Wert, den der return fnode zurückgibt, auch schön fleißig weiterreichen ;)
nochmal:

Code: 
#include <stdio.h>
int test(int num)
{
   printf("test vor dem rekursiven Aufruf %d \n",num);
   if (num>0) test(num-1);
   printf("test danach %d \n",num);
   return num;
}

int test2(int num)
{
   printf("test2 vor dem rekursiven Aufruf %d\n",num);
   if (num>0) return test2(num-1);
   printf("test2 danach %d\n",num);
   return num;
}

int main()
{
 
 printf("Funktionsreturn test: %d \n",test(3));
 printf("Funktionsreturn test2: %d \n",test2(3));
 return 0;
}
Ausgabe:
test vor dem rekursiven Aufruf 3
test vor dem rekursiven Aufruf 2
test vor dem rekursiven Aufruf 1
test vor dem rekursiven Aufruf 0
test danach 0
test danach 1
test danach 2
test danach 3
Funktionsreturn test: 3
test2 vor dem rekursiven Aufruf 3
test2 vor dem rekursiven Aufruf 2
test2 vor dem rekursiven Aufruf 1
test2 vor dem rekursiven Aufruf 0
test2 danach 0
Funktionsreturn test2: 0
Zum Vergrößern anklicken....


Warum solche Unterschiede, obwohl beide Funktionen fast gleich ausschauen?
Bei der ersten wird folgendes gemacht: sofern num größer 0, wird die Funktion selbst aufgerufen,
sonst wird returnt. Wenn man nun 3 eingibt:
Ersetzen wir mal die Variable num mit dem echten Wert:

Code: 
Tiefe:0
   printf("test vor dem rekursiven Aufruf %d \n",3);
   if (3>0) test(2-1); -> aufruf von sich selbst:
Tiefe:1   
       printf("test vor dem rekursiven Aufruf %d \n",2);
       if (2>0) test(2-1);  -> aufruf von sich selbt:
Tiefe:2          
               printf("test vor dem rekursiven Aufruf %d \n",1);
               if (1>0) test(1-1);               
Tiefe:3               
                      printf("test vor dem rekursiven Aufruf %d \n",0);
                      if (0>0) kein Aufruf - weiter machen:
                       printf("test2 danach %d\n",0);
                       return 0; -> rückkehr zurück -> nicht in die Main, sondern zum Aufrufer -> Tiefe2
               
               
               printf("test2 danach %d\n",1);
               return 1; -> rückkehr zur Tiefe 1
               
        printf("test2 danach %d\n",2);
        return 2; -> rückkehr zur Tiefe 0
        
   printf("test2 danach %d\n",3);
   return 3; -> rückkehr zur Main
Die Funktion kommt zwar bis zum Wert 0 - allerdings wird damit nichts gemacht. Return wird immer der für den Aufrufer aktueller Wert - und das ist beim letzten Return die 3 (der Originalwert).

Test2 reicht dagegen den Wert weiter:

Code: 
Tiefe 0:
   printf("test2 vor dem rekursiven Aufruf %d\n",3);
   if (3>0) return test2(3-1);  -> Aufruf von sich selbst
Tiefe 1:
        printf("test2 vor dem rekursiven Aufruf %d\n",2);
        if (2>0) return test2(2-1);  -> Aufruf von sich selbst
Tiefe 2:        
            printf("test2 vor dem rekursiven Aufruf %d\n",1);
            if (1>0) return test2(1-1);  -> Aufruf von sich selbst
Tiefe 3:            
                   printf("test2 vor dem rekursiven Aufruf %d\n",1);
                   if (0>0) kein Aufruf,mache weiter:
                   printf("test2 danach %d\n",0);
                   return 0;  -> return Wert an den Aufrufer in Tiefe 2
            
            return Rückgabe des Aufrufs=0 an den Aufrufer in Tiefe 1
            
         return Rückgabe des Aufrufs=0 an den Aufrufer in Tiefe 0
         
    return Rückgabe des Aufrufs=0 an den Aufrufer -> in Main
test2 returnt also direkt den Wert, anstatt mit den verbliebenen Anweisungen weiterzumachen - daher wird auch printf("danach") nur einmal ausgeführt und der return Wert nicht durch den Aufrufer überschrieben.

Versuche mal mit diesem Link (Absatz: "programmiersprachliche Mechanismen"):
http://www.mi.uni-koeln.de/c/mirror...~schieder/programmieren-2-ss97/recursion.html
Edit: den link vergessen.
 
da ich jetzt gleich kochen werde, schau ich mir gleich dein obigen post an, habs zwischenzeitlich aber erstmal iterativ gelöst:

ich meld mich dann wenn ichs gelesen hab ;) dnake für deine bemühung, bin mir sicher daraus lern ich =)

Code: 
node* tree::insert_find(node *fnode, int wert){ // fängt mit root an und geht hoch und runter
// FUCK Rekursion :P ist scheiße, hier dann doch lieber iterativ:
// scheint bis jetzt konsistenz (weiter prüfungungen stehen noch aus)
	do{
	// gibt es nachfolger? wenn nein, einfach return
	if(fnode->left == nullnode && fnode->right == nullnode) return fnode;

	// prüfen, ob links/rechts eingefügt werden kann
	if(fnode->data > wert && fnode->left == nullnode) return fnode;
	if(fnode->data < wert && fnode->right == nullnode) return fnode;


	// wenn die 3 obigen selektionen keinen erfolg haben, richtige stelle zum springen finden
	if(fnode->data > wert && fnode->left != nullnode) fnode = fnode->left;
	else if(fnode->data < wert && fnode->right != nullnode) fnode = fnode->right;

	}
	while(1); // schade das endlosschleife, aber rekursion macht mich wahnsinnig
}
 
Zum lernen ist die verwendung von rekursion ne gute idee. Du solltest aber wissen, dass die iterative variante schneller ist und im gegensatz zur rekursiven variante mit beliebig tiefen bäumen funktioniert. Bei rekursion wird dir irgendwann der stack zu klein.
 
hallo arno,

das iteration schneller ist, ist mir auch bewusst. da ich aber (wie schon richtig erkannt) rekursion auch beherrschen will (momentan beherrscht die rekusion mich *lol*), wollte ich eben mehr rekursion verwenden um es einfach zu lernen wie es geht ;-)

so, ich vertief mich mal in CDWs post und bedanke mich schonmal!


update:

hab's mir durchgelesen und theoretisch verstanden :)
morgen werde ich defintiv die rekursion wieder implementieren und hoffen, das es funktioniert :-)

also danke für deine mühen cdw! besten dank. =)
 
Hab den Link ganz vergessen:
http://www.mi.uni-koeln.de/c/mirror...~schieder/programmieren-2-ss97/recursion.html

Zu der Rekursion vs. Iteration: es gibt Algorithmen, die sich nur schwer iterativ umsetzen lassen ;). Dabei macht man dann i.R auch deutlich mehr Fehler (da man mehr Code hat).
Dass der Stack irgendwann zu klein ist, kann man imho öfters getrost vergessen. Denn dann hat man ganz andere Probleme.
Z.B hier: binäre Suche rekursiv vs. iterativ:

nehmen wir mal an, dass jeder Aufruf der Suchfunktion 36 Bytes Stack belegt. Nehmen wir auch an, jeder Knoten speichert eine 32 Bit Zahl (also 4 Bytes). Wir haben einen gut balansierten Baum mit einer Tiefe von 32. Nun wollen wir etwas suchen, was unglücklicherweise in der untersten Ebene liegt:
Bei 32 Aufrufen haben wir durch Rekursion 1152 Bytes belegt, gegenüber 36 Bytes iterativ.
Jedoch: bei einer Tiefe von 32 hat unser Baum 4294967295 Knoten. Pro Knoten 4 Bytes Information + 8 Bytes für Links/Rechtszeiger = 51539607552 Bytes =48 GB. Unser Baum belegt also 48GB Speicher. Wenn man Links/Rechtszeiger nicht berücksichtigt (weil man z.B ein Array als Datenstruktur verwendet, auf dem man eine binäre Suche macht) - es sind immer noch 4 GB. Muss man sich da wirklich Sorgen um die 1000 zusätzlichen Bytes machen ;) ?
 
Du hast schon recht, bei binary trees ist das stackproblem irrelevant. Bei rekursiv definierten zahlenfolgen, wird der stack dann schon eher zum Problem. Solange der implementierungsaufwand von itertiver und rekursiver variante annähernd gleich ist (das ist er bei vielen algorithmen), ist die iteration vorzuziehen.

Ob man nun bei der iteration oder bei der rekursion mehr fehler macht, ist sicherlich vom programmierer abhängig.
 
so,

also nochmal danke CDW für die guten hinweise =D
damit hatte ich die rekursion theoretisch verstanden (hat mir geholfen!) aber die praxis sah wieder mal schlecht aus.

da ich ja als studentische hilfskraft bei nem' spieleentwickler arbeite (als bug-tester, echt cooler job finde ich) fragte ich einfach mal einen programmierer zum thema rekursion.

dann hatte ich ihm vom spezifischem problem erzählt und er meinte, das es schon zuviele zeilen hätte ;-)
das brachte mich zum nachdenken und das, was ich dann über die links erfahren hatte kombiniert und rauskam:

Code: 
node* tree::insert_find(node *fnode, int wert){
	if(fnode->data < wert && fnode->right != nullnode) return insert_find(fnode->right, wert);
	if(fnode->data > wert && fnode->left != nullnode) return insert_find(fnode->left, wert);
	return fnode;
}

und siehe da - funktioniert :)
das beste ist noch, das es beim ersten versuch geklappt hat ud ich war mir auch sicher das es funktionieren muss. *yay* :-P


also thx nochmal,

"schleichwerbung-mode-an"
btw die firma ist www.ascaron.com und ich arbeite tatkräftig bei:
www.sacred2.de mit :-)

tolles spiel, unbedingt kaufen ;-)
"schleichwerbung-mode-aus"
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben