Hallo zusammen, ich habe mir eine Datenstruktur gebaut, die über eine Baumstruktur ein LCD-Menü abbildet (also mit Kategorien, Unterkategorien, Attributen, Funktionen, usw.). Nun bin ich gerade dabei eine init()-Prozedur zu schreiben, die diesen Baum vorab mal komplett durchlaufen soll, um eventuelle Voreinstellungen zu tätigen. Da diese Baumstruktur nicht balanciert ist (der Horizont erstreckt sich über mehrere Ebenen) hab ich mir gedacht, mach ich den Durchlauf rekursiv. Nun wollte ich fragen, ob man beim GCC etwas besonderes beachten muss z.B. unterstützt er "tail recursion"? Vielen Dank schon mal :-)
Bei Rekursionen ne Abbruchbedingung nicht vergessen, sonst läuft der Stack über. Rekursionen werden in der Regel sehr schlecht optimiert (haufenweise unnötige PUSHs/POPs). Der Compiler kann halt den Sinn einer Funktion nicht verstehen. Meistens ists daher über ne Schleife schneller, üübersichtlicher und weniger Code. Wenn die Initialisierung eh schon zur Compilezeit feststeht, dann laß es doch einfach den Compiler machen, ist mit Abstand am effektivsten. Standardmäßig wird ja alles mit 0 initialisiert. Peter
Hallo Peter, vielen Dank für die Infos. Ich hab die Routine wie oben geschildert nun mal umgesetzt und sie funktioniert eigentlich auch Tiptop :-) So kann ich jetzt beliebig tiefe Bäume durchlaufen. Das über Schleifen zu machen wäre etwas umständlich, oder? Ich finde es eigentlich so relativ kompakt und auch gut verständlich. Hier mal das Sniplett: void init(node *e, int8_t ind) { if (ind == -1) //Abbruch return; else { if (e->kids[ind]->nodemode == SELECTION) //Eintrag ist Init-relevant { //Initialiserung aufgrund vom Auswahlwert im EEPROM } else if (e->kids[ind]->nodemode == CATEGORY) //Unterkategorien { //Rekursion auf Unterkategorie und evtl. deren Unterkategorie init(e->kids[ind]->pEntry,9); } init(e,--ind); //Rekursion: Alle weiteren Einträge dieser Kategorie } } Viele Grüße Peter (der Namensvetter :-))
Hi beliebig tief nicht da dir der Stack auf den AVRs recht fix ausgeht wenn kein externes RAM dranhängt. Matthias
> beliebig tief nicht da dir der Stack auf den AVRs recht > fix ausgeht wenn kein externes RAM dranhängt. Ich weiß nicht, wie weit der gcc das auf der AVR-Architektur schafft, aber normalerweise kann er tail recursion erkennen und entsprechend optimieren. Dann wird der Stack durch die Rekursion nicht mehr beansprucht. Allerdings hat MuesLee nicht überall Endrekursion verwendet, die Zeile "init(e->kids[ind]->pEntry,9);" ist eine "normale" Rekursion, die den Stack fordert.
Guck dir doch den Assemblercode an, der generiert wird. Meiner Meinung nach wird eine tail recursion nicht wegoptimiert.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.