Rekursive Procedure-Calls

[MuesLee (Gast)]

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 :-)

[Peter D. (peda)]

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

[MuesLee (Gast)]

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 :-))

[Μαtthias W. (matthias)]

Hi

beliebig tief nicht da dir der Stack auf den AVRs recht fix ausgeht wenn 
kein externes RAM dranhängt.

Matthias

[Chris (Gast)]

> 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.

[Jörg W. (dl8dtl) (Moderator)]

Guck dir doch den Assemblercode an, der generiert wird.

Meiner Meinung nach wird eine tail recursion nicht wegoptimiert.