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.
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
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. 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.
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
unsignedsum(unsignedn)
2
{
3
returnn?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
structBaum
2
{
3
charwert;
4
structBaum*left,*right;
5
};
6
7
charbaum_summe(conststructBaum*b)
8
{
9
returnb
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.
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
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
>unsignedsum(unsignedn)
2
>{
3
>returnn?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
unsignedsum_tr(unsignedn,unsignedaccum)
2
{
3
if(!n)
4
returnaccum;
5
else
6
returnsum_tr(n-1,accum+n);
7
}
8
9
10
unsignedsum(unsignedn)
11
{
12
returnsum_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