Rekursive Procedure-Calls

MuesLee Gast #464102
Lesenswert?
• ▲
▼ 
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 :-)
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
Peter D. #464110
Lesenswert?
• ▲
▼ 
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
Antwort Zitieren Bearbeiten Löschen Beitrag melden
MuesLee Gast #464166
Lesenswert?
• ▲
▼ 
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 :-))
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Chris Gast #464246
Lesenswert?
• ▲
▼ 
> 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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt. Bitte hier nur auf die ursprüngliche Frage antworten, für neue Fragen einen neuen Beitrag erstellen.

Formatierung
  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Dein Name und deine E-Mail-Adresse

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.