? zu rekursiven Funktionsaufrufen

[Thomas P. (topla)]

Moin,

ich bin bei meiner Programmierung auf das Thema "rekursive 
Funktionsaufrufe" gelaufen. Soweit auch kein Problem, wenn eine Funktion 
der Art foo() benutzt wird. Auch das Begrenzen der Anzahl der 
Rekursionen ist klar.

Ich habe jetzt aber als Anfänger ein Verständnisproblem, wie mit 
Funktionen umgegangen werden muss, die intern einen Schleifenzähler 
benötigen und einen Rückgabewert liefern.

Den Teil "Rückgabewert" kann man wohl mit einer globalen Variable bzw. 
mit static lösen. Ist das richtig oder bin ich da auf dem Holzweg?

Der Schleifenzähler der aktuellen Ebene hingegen muss ja jeden weiteren 
rekursiven Aufruf überleben, das können also n verschiedene Werte 
werden, die ich in Assembler einfach bei jeder Rekursion auf den Stack 
sichern würde. Aber wie macht man das in C?

Danke für alle Hinweise,
Thomas

[Peter D. (peda)]

Rekursion sieht nur auf dem Papier hübsch aus. Auf der CPU bewirkt der 
ständige CALL/RET/PUSH/POP Ballast erheblichen RAM- und CPU-Verbrauch.
Wenn es irgendwie geht, die Rekursion besser in eine Schleife umformen.

Ich hatte auch mal ne Rekursion hingeschrieben und war ganz verblüfft, 
daß der GCC es als Schleife implementiert hatte.

[Christian S. (roehrenvorheizer)]

Hallo,

was Du in Assembler fehlerfrei durch Dein Geschick bei der 
Programmierung erledigen mußt, macht in C der Compiler für Dich von 
selbst.

Siehe:
http://www.c-howto.de/tutorial/funktionen-teil-2/rekursion/

mfG

[Captain Albern (Gast)]

Thomas P. schrieb:
> Der Schleifenzähler der aktuellen Ebene hingegen muss ja jeden weiteren
> rekursiven Aufruf überleben, das können also n verschiedene Werte
> werden, die ich in Assembler einfach bei jeder Rekursion auf den Stack
> sichern würde. Aber wie macht man das in C?

Darum kümmert sich der Compiler. Der aktuelle Schleifenzähler wird auf 
den Stack geschrieben, bevor die Funktion sich wieder selbst aufruft. 
Der Schleifenzähler in der nächsten Rekursionsebene heißt zwar gleich, 
ist aber eine neue Instanz (wenn man das Wort hier benutzen darf) einer 
lokalen Variable.

[Basti B. (basti195)]

Den Rückgabe wert kannst du auch über die Rekursion erledigen und dir 
somit eine Globale Variable sparen.
Bsp.

int add5Times1(int i,count){
  if(count == 5){
    return i
  }
  else
    return add5Times1(i+1,count+1)
}

[Felix F. (wiesel8)]

Wenns um Embedded geht, würde ich Rekursion ganz vermieden, da dadurch 
der Stack sehr schnell anwachsen kann, welcher bei Mikrocontroller 
sowieso schon verdammt klein ist.

mfg

[Thomas P. (topla)]

Danke an Alle für die Informationen, muss ich jetzt erstmal 
nachvollziehen.
Im Prinzip ist die Rekursion hier ein Versuch, mal in das Thema 
einzusteigen. Es wird ein Baum durchsucht und verschiedene Aktionen 
ausgelöst. Die Tiefe beträgt maximal 5 Ebenen, dann breche ich ab und 
damit sollte die Stackbelastung im Rahmen bleiben. Das Listing vermeldet 
4 push/pop + call/ret pro Aufruf und das wird wohl für den verwendeten 
ATMega2560 keine zu große Aufgabe sein.

Thomas

[c-hater (Gast)]

Thomas P. schrieb:

> Die Tiefe beträgt maximal 5 Ebenen

Wenn die maximale Tiefe vorher bekannt ist, braucht man ganz sicher 
keine Rekursion, dann kann man das immer einfachst in eine Schleife 
umformen.

Rekursive Algorithmen ergeben nur dann irgendeinen Sinn, wenn die 
Rekursionstiefe eben nicht bekannt ist.

Aber natürlich kann man auch diese Algorithmen zur Schleife umformen. 
Was den RAM-Verbrauch angeht, besteht der Unterschied zwischen Rekursion 
und Schleife aber einzig und allein darin, dass bei der Schleife das 
Speichern/Laden der Return-Adresse eingespart werden kann.
Alles andere für den Algorithmus Wichtige muss natürlich in beiden 
Fällen gleichermaßen pro "Rekursionsebene" gespeichert werden, hier 
ergibt sich also prinzipiell keinerlei Unterschied im Speicherbedarf. 
Maximal in Hinsicht darauf, dass man bei der Schleifenvariante 
prinzipiell die Wahl hat, ob man Stack oder Heap wachsen läßt. Das ist 
aber ein rein akademischer Unterschied, wenn der Heap in den Stack 
knallt ist das Ergebnis nämlich ganz genauso schlimm als wenn der Stack 
in den Heap knallt...

[Christian S. (roehrenvorheizer)]

Rekursion lief bei mir schon auf dem AT90S2313 zur Steuerung einer PLL 
mittels Schieberegistern.

MfG

[Peter D. (peda)]

Christian S. schrieb:
> Rekursion lief bei mir schon auf dem AT90S2313 zur Steuerung einer PLL
> mittels Schieberegistern.

Es hat auch niemand das Gegenteil behauptet. Nur, daß es mehr Ressourcen 
benötigt gegenüber einer Schleife.
Oftmals ist eine Schleife auch besser zu durchschauen als eine 
Rekursion.
Bei ner Rekursion habe ich immer das Gefühl, ich müßte mich an der 
Stiefelstrippe aus dem Sumpf ziehen.
Die meisten Compiler für Architekturen mit Softwarestack können 
Rekursionen.
Z.B. alle 8051 und AVR (außer AT90S1200, ATtiny12, 15).

[Thomas P. (topla)]

Peter D. schrieb:
> Bei ner Rekursion habe ich immer das Gefühl, ich müßte mich an der
> Stiefelstrippe aus dem Sumpf ziehen.

Ja, das Gefühl habe ich jetzt auch, nachdem ich versucht habe, den 
Programmablauf nachzuvollziehen, scheint aber zu funktionieren. Auf der 
Zielhardware kann ich das erst am Wochenende probieren. An der Stelle 
habe ich den Compiler deutlich unterschätzt.

Der Programmierer der abzulösenden Softwareversion hat die Tiefe auf 2 
Ebenen beschränkt und die Funktionsaufrufe der beiden Ebenen durch 
Kopieren der Funktion gelöst - also nichts mit Rekursion.

Ich wollte es halt mal probieren, auch weil ich die Anzahl der Ebenen 
erhöhen wollte und das Abarbeiten des Baums so recht elegant zu lösen 
ist.

Thomas

[Rolf M. (rmagnus)]

c-hater schrieb:
> Das ist aber ein rein akademischer Unterschied, wenn der Heap in den Stack
> knallt ist das Ergebnis nämlich ganz genauso schlimm als wenn der Stack
> in den Heap knallt...

Gerade wenn du die Anzahl der Durchläufe vorher nicht kennst, macht das 
sehr wohl einen Unterschied. Wenn du immer wieder reallokieren musst, 
hast du temporär einen wesentlich höheren Speicherverbrauch.

[Eric B. (beric)]

Ein Beispiel sagt mehr als 1000 Wörter ;-)

/* Definier einen (binären) Baum */
struct Baum {
  int          wert;
  struct Baum *l_ast;
  struct Baum *r_ast;
};

/* klettere durch den baum und addiere alle gefundene Werte */
int baum_wert(struct Baum *b)
{
  int summe = 0;

  if (b != NULL)
  {
    summe = b->wert 
          + baum_wert(b->l_ast) /* <-- rekursive Aufrufe */
          + baum_wert(b->r_ast);
  }

  return summe;
}

[Johann L. (gjlayde)]

Mal 2 konkrete Beispiele, wie ein Compiler das umsetzen kann; hier mit 
avr-gcc-7 -O2 ... Bei Optimierung auf Codegröße ist der Code fast 
identisch.  Beispiel #1 berechnet die Summe der ersten n ganzen Zahlen 
>= 0

unsigned sum (unsigned n)
{
    return n ? n + sum (n - 1) : 0;
}

Die Funktion ist end-rekursiv, und daher kann sie in eine Schleife 
umgewandelt werden:

sum:
  ldi r19,0
  ldi r18,0
  sbiw r24,0
  breq .L1
.L3:
  add r18,r24
  adc r19,r25
  sbiw r24,1
  brne .L3
.L1:
  movw r24,r18
  ret

Beipiel #2 ist die Summe über alle Einträge einers binären Baums wie von 
oben, nur dass der Code etwas ungewohnt formatiert ist damit gcc die 
Quellzeilen besser dem Compilat zuordnen kann:

struct Baum
{
  char wert;
  struct Baum *left, *right;
};

char baum_summe (const struct Baum *b)
{
  return b
    ? b->wert
      + baum_summe (b->left)
      + baum_summe (b->right)
    : 0;
}

baum_summe ist nicht end-rekursiv, aber immerhin kann 1 Aufruf von 
baum_summe in eine Schleife umgewandelt werden.  Daher verbleibt ein 
Aufruf, und auch im Compilat stellt sich die Funktion rekursiv dar:

baum_summe:
  push r16
  push r17
  push r28
  push r29
/* prologue: function */
  movw r28,r24   ;  b, b
 ;  foo.c:13:     : 0;
  ldi r17,0   ;  <retval>
  or r24,r25   ;  b
  breq .L1
.L3:
 ;  foo.c:10:     ? b->wert
  ld r16,Y   ;  _2, b_19->wert
 ;  foo.c:11:       + baum_summe (b->left)
  ldd r24,Y+1   ; , b_19->left
  ldd r25,Y+2   ; , b_19->left
  call baum_summe   ; 
 ;  foo.c:12:       + baum_summe (b->right)
  ldd __tmp_reg__,Y+3   ;  b_19->right
  ldd r29,Y+4   ;  b, b_19->right
  mov r28,__tmp_reg__   ;  b
  add r17,r24   ;  tmp53,
  add r17,r16   ;  <retval>, _2
 ;  foo.c:13:     : 0;
  sbiw r28,0   ;  b,
  brne .L3
.L1:
 ;  foo.c:14: }
  mov r24,r17   ; , <retval>
/* epilogue start */
  pop r29
  pop r28
  pop r17
  pop r16
  ret

Hier ist eine rekursive Funktion mindestend angebracht, denn sie 
operiert auf einer (nicht linear) rekursiven Datenstruktur. Auf Anhieb 
sehe auch nicht, wie die Rekursion komplett in eine Schleife umgewandelt 
werden kann, ohne eine entsprechende Verwaltung händisch zu 
implementieren; etwa durch einen eigenes (sogar teureres) Stack-Objekt.

[Hunsbuckel (Gast)]

Es werden immer wieder irgendwelche Säue von den Informatik-Professoren 
durchs Dorf getrieben

Mal muss alles irgendwie rekursiv gemacht werden

Ein anderes mal muss jedes noch so simple Programm irgendwie 
objektorientiert vergewaltigt werden

Usw. Usw.

Es gibt Sachen, die genial rekursiv gelöst werden können - aber das ist 
im ( meinem ) realen Leben eher selten

[Vincent H. (vinci)]

Die neue Sau? Rekursion ist älter als jedes Schleifenkonstrukt...

[Ruediger A. (Firma: keine) (rac)]

Johann L. schrieb:
> Mal 2 konkrete Beispiele, wie ein Compiler das umsetzen kann; hier mit
> avr-gcc-7 -O2 ... Bei Optimierung auf Codegröße ist der Code fast
> identisch.  Beispiel #1 berechnet die Summe der ersten n ganzen Zahlen
>>= 0
>

> unsigned sum (unsigned n)
> {
>     return n ? n + sum (n - 1) : 0;
> }
>

> Die Funktion ist end-rekursiv, und daher kann sie in eine Schleife
> umgewandelt werden:
>

> sum:
>   ldi r19,0
>   ldi r18,0
>   sbiw r24,0
>   breq .L1
> .L3:
>   add r18,r24
>   adc r19,r25
>   sbiw r24,1
>   brne .L3
> .L1:
>   movw r24,r18
>   ret
>

uhm, das ist so nicht richtig. Die Funktion ist so wie sie in C 
formuliert ist nicht endrekursiv, weil das Ergebnis des rekursiven 
Aufrufes nicht das Ergebnis der aufrufenden Funktion ist (Definition 
Endrekursion). Der Compiler scheint hier die Transformation in eine 
endrekursive Form selber vornehmen zu können, aber in C geschrieben wäre 
sie erst in dieser Form endrekursiv:

unsigned sum_tr (unsigned n,unsigned accum)
{
    if (!n) 
        return accum;
    else
        return sum_tr (n - 1,accum+n);
}


unsigned sum (unsigned n)
{
    return sum_tr(n,0);
}

In komplexeren Beispielen wird der Compiler mglw. die Endrekursion nicht 
erkennen und die Transformation demzufolge nicht selber machen, erst in 
explizit endrekursiver Form.

(sh. https://en.wikipedia.org/wiki/Tail_call).

Die Rekursionstheorie ist keineswegs nur eine Sau, die durchs Dorf 
getrieben wird, sondern ein komplett eigenständiger Ansatz, 
Kontrollstrukturen zu verstehen und umzusetzen (Scheme beruht zu einem 
starken Teil auf den Erkenntnissen der Rekursionstheorie).

Jede Funktion kann komplett Endrekursiv umgeschrieben werden (wobei aber 
in manchen Fällen, z.B. in dem erwähnten Baumbeispiel, zusätzliche 
Tricks wie Continuation Passing angewendet werden müssen).

[Thomas P. (topla)]

Moin zusammen,

nun ist es so gekommen, wie Peter das vorhergesehen hat – ich stehe 
mitten im Wald und versuche, mich am Stiefelband aus dem Sumpf zu 
ziehen.

Durch Johanns Ausführungen weiß ich jetzt zumindest, dass mein Problem 
nicht endrekursiv ist und sich wohl nicht ohne weiteres in eine Schleife 
entrollen lässt. Ich hoffe, ich habe das richtig verstanden.

Ich habe hier bis zu 256 Datensätze mit jeweils bis zu 16 Einträgen der 
Typen „W“ und „F“. Ein Eintrag mit der Kennung „W“ kann mit einer 
Funktion (existiert und funktioniert) geprüft werden – Rückgabe „0“ für 
ok, 0xff für fehlerhaft. Ein Eintrag mit der Kennung „F“ zeigt jetzt 
aber auf einen anderen Datensatz, dessen Einträge wiederum mit den 
Kennungen „W“ und „F“ versehen sein können. Hier soll die Rekursion zum 
Einsatz kommen und ich weiß nicht, wie ich das anpacken soll.

Ist eine der Prüfungen nicht ok, soll der ganze Vorgang abgebrochen und 
das Fehlerkennzeichen (ggf. also über mehrere Ebenen) zurückgegeben 
werden, ebenfalls dann, wenn die Rekursion die Tiefe 5 übersteigt (das 
ist dann fachlich nicht mehr sinnvoll).

Ich bitte um Hilfe (und darum, den ersten Teil mit den üblichen 
Beschimpfungen als Depp wegzulassen)…

Thomas

[Yalu X. (yalu) (Moderator)]

In einem Kauderwelsch aus C und Pseudocode könnte das etwa so aussehen:

#define MAX_RECURSION_DEPTH 5

typedef enum { E_OK, E_INVALID_W, E_MAX_RECURSION_DEPTH_EXCEEDED } error_t;

int checkW(entry_t);  // existing function for checking a W type entry

error_t checkEntry(entry_t entry, int depth) {
  // check an entry recursively
  error_t error;

  if (depth >= MAX_RECURSION_DEPTH)
    error = E_MAX_RECURSION_DEPTH_EXCEEDED;
  else if (entry is of type W) {
    if (checkW(entry) == 0)
      error = E_OK;
    else // 0xff
      error = E_INVALID_W;
  }
  else {
    // entry is of type F
    for (subEntry in subEntries(entry)) {
      error = checkEntry(subEntry, depth+1)
      if (error != E_OK)
        break;
    }
  }
  return error;
}

// apply checkEntry():

error_t error checkEntry(entry, 0);
switch (error) {
  case E_OK:
    printf("ok\n");
    break;
  case E_INVALID_W:
    printf("invalid W entry\n");
    break;
  case E_MAX_RECURSION_DEPTH_EXCEEDED:
    printf("maximum recursion depth exceeded\n");
    break;
  default:
    printf("invalid error code\n");
}

[Thomas P. (topla)]

Danke, ich glaube, jetzt komme ich damit klar.
Mal schauen, wo die nächste Frage lauert...

Thomas