Rekursive Procedure-Calls

Gast #464102 
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 Langsamer Modus Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Melden Danke 
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 Melden Danke
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 :-))
Antwort Zitieren Bearbeiten Löschen Melden Danke
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.
Antwort Zitieren Bearbeiten Löschen Melden Danke
Thread beobachten

Antwort schreiben

Eine eigene Frage? Dieser Thread ist über 19 Jahre alt. Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.

Neuen Thread starten

Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.

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.