www.mikrocontroller.net

Forum: Compiler & IDEs Rekursive Procedure-Calls


Autor: MuesLee (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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 :-)

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: MuesLee (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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 :-))

Autor: Μαtthias W. (matthias) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi

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

Matthias

Autor: Chris (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Guck dir doch den Assemblercode an, der generiert wird.

Meiner Meinung nach wird eine tail recursion nicht wegoptimiert.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
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.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.