Rekursions Beseitigung
-
Hallöle
Ich habe vollgendes Problem eine Rekursion macht bei mir Probleme und verursacht ein Stack Überlauf und meine Frage ist wie kriege ich die Rekursion da raus.
Es geht um einen BinärensuchbaumHier der Code
bool baum::vorh(knoten *k, int x) { if (x==k->out_inhalt()) return true; //gefunden else if (x<k->out_inhalt()) { //suche links if (k->out_lsohn()!=0) return vorh(k->out_lsohn(),x); else return false; } else { //suche rechts if (k->out_rsohn()!=0) return vorh(k->out_rsohn(),x); else return false; } }
-
Du bekommst die Rekursion da raus indem Du den Aufruf von vorh aus vorh herausnimmst.
Das wird aber wohl nicht Dein Problem lösen. Der Code sieht auch an sich i.O. aus (insoweit dass die Rekursion bei einem echten Baum irgendwann terminiert). Ich denke Du musst herausfinden warum in dem Baum zirkuläre Referenzen existieren.
-
Hallo nochmal!
So ich habe keine Ahnung wo dieser Fehler ist.
Ich weiss nur das mein Baum bis ca.5000 Elemente richtig funktioniert
und dann durch die Rekursion in vorh eine Owerflow passiert.
Kenn ihr vielleicht ein Iteratives verfahren um den Baum zu durchlaufen
-
Achso, ja dann scheint tatsächlich der Stack zu klein zu sein (dachte zuerst, ein fehlerhafter Baum löst die Rekursion aus).
Im Wesentlichen kannst Du sowas machen um den Baum iterativ zu durchforsten:
bool baum::vorh(knoten *k, int x) { while (k) { if (x == k->out_inhalt()) // gefunden return true; if (x < k->out_inhalt) k = k->out_lsohn(); else k = k->out_rsohn(); } return false; }Also so lange die Söhne durchsuchen bis a) etwas gefunden wurde (springt direkt aus der Schleife heraus) oder b) ein Blatt erreicht wurde (Schleifenbedingung nicht mehr erfüllt).
-
Benutze das gleiche Verfahren, aber iterativ formuliert.
Bye, TGGC (Fakten)
