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
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.
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
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.
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) }
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
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
:
Bearbeitet durch User
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...
Rekursion lief bei mir schon auf dem AT90S2313 zur Steuerung einer PLL mittels Schieberegistern. MfG
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).
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
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.
Ein Beispiel sagt mehr als 1000 Wörter ;-)
1 | /* Definier einen (binären) Baum */
|
2 | struct Baum { |
3 | int wert; |
4 | struct Baum *l_ast; |
5 | struct Baum *r_ast; |
6 | };
|
7 | |
8 | /* klettere durch den baum und addiere alle gefundene Werte */
|
9 | int baum_wert(struct Baum *b) |
10 | {
|
11 | int summe = 0; |
12 | |
13 | if (b != NULL) |
14 | {
|
15 | summe = b->wert |
16 | + baum_wert(b->l_ast) /* <-- rekursive Aufrufe */ |
17 | + baum_wert(b->r_ast); |
18 | }
|
19 | |
20 | return summe; |
21 | }
|
:
Bearbeitet durch User
Beitrag #5336610 wurde von einem Moderator gelöscht.
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
1 | unsigned sum (unsigned n) |
2 | {
|
3 | return n ? n + sum (n - 1) : 0; |
4 | }
|
Die Funktion ist end-rekursiv, und daher kann sie in eine Schleife umgewandelt werden:
1 | sum: |
2 | ldi r19,0 |
3 | ldi r18,0 |
4 | sbiw r24,0 |
5 | breq .L1 |
6 | .L3: |
7 | add r18,r24 |
8 | adc r19,r25 |
9 | sbiw r24,1 |
10 | brne .L3 |
11 | .L1: |
12 | movw r24,r18 |
13 | 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:
1 | struct Baum |
2 | {
|
3 | char wert; |
4 | struct Baum *left, *right; |
5 | };
|
6 | |
7 | char baum_summe (const struct Baum *b) |
8 | {
|
9 | return b |
10 | ? b->wert |
11 | + baum_summe (b->left) |
12 | + baum_summe (b->right) |
13 | : 0; |
14 | }
|
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:
1 | baum_summe: |
2 | push r16 |
3 | push r17 |
4 | push r28 |
5 | push r29 |
6 | /* prologue: function */ |
7 | movw r28,r24 ; b, b |
8 | ; foo.c:13: : 0; |
9 | ldi r17,0 ; <retval> |
10 | or r24,r25 ; b |
11 | breq .L1 |
12 | .L3: |
13 | ; foo.c:10: ? b->wert |
14 | ld r16,Y ; _2, b_19->wert |
15 | ; foo.c:11: + baum_summe (b->left) |
16 | ldd r24,Y+1 ; , b_19->left |
17 | ldd r25,Y+2 ; , b_19->left |
18 | call baum_summe ; |
19 | ; foo.c:12: + baum_summe (b->right) |
20 | ldd __tmp_reg__,Y+3 ; b_19->right |
21 | ldd r29,Y+4 ; b, b_19->right |
22 | mov r28,__tmp_reg__ ; b |
23 | add r17,r24 ; tmp53, |
24 | add r17,r16 ; <retval>, _2 |
25 | ; foo.c:13: : 0; |
26 | sbiw r28,0 ; b, |
27 | brne .L3 |
28 | .L1: |
29 | ; foo.c:14: } |
30 | mov r24,r17 ; , <retval> |
31 | /* epilogue start */ |
32 | pop r29 |
33 | pop r28 |
34 | pop r17 |
35 | pop r16 |
36 | 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.
:
Bearbeitet durch User
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
Die neue Sau? Rekursion ist älter als jedes Schleifenkonstrukt...
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 >
1 | > unsigned sum (unsigned n) |
2 | > { |
3 | > return n ? n + sum (n - 1) : 0; |
4 | > } |
5 | >
|
> Die Funktion ist end-rekursiv, und daher kann sie in eine Schleife > umgewandelt werden: >
1 | > sum: |
2 | > ldi r19,0 |
3 | > ldi r18,0 |
4 | > sbiw r24,0 |
5 | > breq .L1 |
6 | > .L3: |
7 | > add r18,r24 |
8 | > adc r19,r25 |
9 | > sbiw r24,1 |
10 | > brne .L3 |
11 | > .L1: |
12 | > movw r24,r18 |
13 | > ret |
14 | > |
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:
1 | unsigned sum_tr (unsigned n,unsigned accum) |
2 | {
|
3 | if (!n) |
4 | return accum; |
5 | else
|
6 | return sum_tr (n - 1,accum+n); |
7 | }
|
8 | |
9 | |
10 | unsigned sum (unsigned n) |
11 | {
|
12 | return sum_tr(n,0); |
13 | }
|
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).
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
In einem Kauderwelsch aus C und Pseudocode könnte das etwa so aussehen:
1 | #define MAX_RECURSION_DEPTH 5
|
2 | |
3 | typedef enum { E_OK, E_INVALID_W, E_MAX_RECURSION_DEPTH_EXCEEDED } error_t; |
4 | |
5 | int checkW(entry_t); // existing function for checking a W type entry |
6 | |
7 | error_t checkEntry(entry_t entry, int depth) { |
8 | // check an entry recursively
|
9 | error_t error; |
10 | |
11 | if (depth >= MAX_RECURSION_DEPTH) |
12 | error = E_MAX_RECURSION_DEPTH_EXCEEDED; |
13 | else if (entry is of type W) { |
14 | if (checkW(entry) == 0) |
15 | error = E_OK; |
16 | else // 0xff |
17 | error = E_INVALID_W; |
18 | }
|
19 | else { |
20 | // entry is of type F
|
21 | for (subEntry in subEntries(entry)) { |
22 | error = checkEntry(subEntry, depth+1) |
23 | if (error != E_OK) |
24 | break; |
25 | }
|
26 | }
|
27 | return error; |
28 | }
|
29 | |
30 | // apply checkEntry():
|
31 | |
32 | error_t error checkEntry(entry, 0); |
33 | switch (error) { |
34 | case E_OK: |
35 | printf("ok\n"); |
36 | break; |
37 | case E_INVALID_W: |
38 | printf("invalid W entry\n"); |
39 | break; |
40 | case E_MAX_RECURSION_DEPTH_EXCEEDED: |
41 | printf("maximum recursion depth exceeded\n"); |
42 | break; |
43 | default:
|
44 | printf("invalid error code\n"); |
45 | }
|
:
Bearbeitet durch Moderator
Danke, ich glaube, jetzt komme ich damit klar. Mal schauen, wo die nächste Frage lauert... Thomas
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.