mikrocontroller.net

Forum: Compiler & IDEs Frage zu Rekursion und StackOverflow in C


Autor: Panzer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Moin,

wenn ich eine Funktion habe die rekursiv arbeitet z.B. um die Fakultät 
zu berechnen:
int fakultaet(int x) {
  if(x > 1) 
  {
    return x * fakultaet(x-1);
  }
  else 
  {
    return 1;
  }
}

habe ich gehört das man irgendwann in ein StackOverflow kommen kann.

Aber doch nur wenn (in diesem Beipsiel) x in diesem Fall zu groß ist 
oder?

Ich kann doch trtzdm diese Funktion "beliebig" oft ausführen solang das 
x klein bleibt, ohne in ein Stack Overflow zu kommen, oder?


Gruß
Panzer

: Verschoben durch Moderator
Beitrag #5645092 wurde von einem Moderator gelöscht.
Autor: Sebi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Je tiefer deine Funktionen verschachtelt sind bzw. je länger die 
Rekursion läuft, umso mehr Platz wird auf dem Stack benötigt. Die Anzahl 
mit der du die Funktion nacheinander aufrufst hat damit nichts zu tun. 
Du kannst also beliebig oft fakultaet(5) berechnen lassen.

Autor: Carl D. (jcw2)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sebi schrieb:
> Je tiefer deine Funktionen verschachtelt sind bzw. je länger die
> Rekursion läuft, umso mehr Platz wird auf dem Stack benötigt. Die Anzahl
> mit der du die Funktion nacheinander aufrufst hat damit nichts zu tun.
> Du kannst also beliebig oft fakultaet(5) berechnen lassen.

Wobei vermutlich die "int"-Bits deutlich früher ausgehen als der Stack.

Autor: g457 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Wobei vermutlich die "int"-Bits deutlich früher ausgehen als der Stack.

x wird nur runtergezählt, da ist das kein Problem. Dass das Ergebnis 
überläuft ist weniger problematisch als der durch den überlaufenden 
Stack verursachte Schaden.

Das ist übrigens der Grund, warum Rekursion grundsätzlich nur mit 
äußerster Vorsicht zu benutzen und vorzugweise immer zu vermeiden ist. 
In obigem Beispiel ist es zwar aus akademischer sich korrekt, praktisch 
aber total überflüssig und fehleranfällig.

Autor: mh (Gast)
Datum:

Bewertung
2 lesenswert
nicht lesenswert
g457 schrieb:
> x wird nur runtergezählt, da ist das kein Problem. Dass das Ergebnis
> überläuft ist weniger problematisch als der durch den überlaufenden
> Stack verursachte Schaden.

x ist nicht das Problem. Der temporäre int ist das Problem. Schon 13! 
hat mehr als 32 bit und man hat dank signed-integer-overflow undefined 
behaviour (32bit ints vorausgesetzt, bei 64bit ist es 21!). Die 
Rekursionstiefe von 13 ist sicher kein Problem. Vor allem da die 
Funktion mit einem ordentlichen Compiler dank tail-recursion keinen 
Stack benötigt (gcc ab -O2 oder -Os.

Autor: Panzer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Vielen Dank, dann habe ich es nun verstanden!

Autor: Peter D. (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Compiler sind nicht ganz sö blöd, wie mancher denkt.
Der AVR-GCC erkennt, daß das eine Schleife ist und erstellt keine 
Rekursion. Der Stackverbrauch ist also 2 Bytes für den Call.

Autor: Peter D. (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
g457 schrieb:
> Das ist übrigens der Grund, warum Rekursion grundsätzlich nur mit
> äußerster Vorsicht zu benutzen und vorzugweise immer zu vermeiden ist.

Daher sollte man immer auch einen Zähler für die maximale 
Schachtelungstiefe mitlaufen lassen, um die Notbremse zu ziehen, wenn es 
denn unbedingt eine Rekursion sein muß.

Autor: Bernd B. (microwave-designer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
... oder das OS fängt das ab.

BR

Bernd

Autor: Yalu X. (yalu) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
mh schrieb:
> Vor allem da die Funktion mit einem ordentlichen Compiler dank
> tail-recursion keinen Stack benötigt (gcc ab -O2 oder -Os.

Hier handelt es sich nicht einmal um eine Tail-Recursion¹, dennoch
schafft der GCC die Entrekursivierung. Solche Optimierungesfähigkeiten
sind aber von Compiler zu Compiler unterschiedlich, deswegen sollte man
sich nicht auf sie verlassen.

———————————
¹) Diese kann ein Compiler mittels Tail-Call-Optimization (Ersetzen
   einer CALL/RET-Kombination durch einen JMP) sehr leicht auflösen.

Autor: Bernd B. (microwave-designer)
Datum:

Bewertung
-2 lesenswert
nicht lesenswert
... eigentlich sollte doch jeder in der Lage sein, eine Rekursion in 
eine "while"-Schleife umzuwandeln - oder auch umgekehrt, wenn nötig.

Lernt man das heute nicht mehr an der Uni?
function fakultaet(const i:integer):integer;
var fak:integer;
begin
   { error treatment outside this function }
   fak:=1;
   while i>1
      begin
         fak:=fak*i;
         i:=i-1
      end;
   fakultaet:=fak
end;


Warnung: ... kann Fehler enthalten - nicht kompiliert!

Smiley

Bernd

Autor: schlaubi (Gast)
Datum:

Bewertung
3 lesenswert
nicht lesenswert
> ... eigentlich sollte doch jeder in der Lage sein, eine Rekursion in
> eine "while"-Schleife umzuwandeln - oder auch umgekehrt, wenn nötig.

Dann zeig das mal fuer das Ackermannsche Funktional,
Herr Universitaeter!

Autor: Rolf M. (rmagnus)
Datum:

Bewertung
2 lesenswert
nicht lesenswert
Bernd B. schrieb:
> Lernt man das heute nicht mehr an der Uni?

Nicht jeder, der hier eine Frage stellt, hat studiert.

Panzer schrieb:
> Ich kann doch trtzdm

Gesundheit!

> diese Funktion "beliebig" oft ausführen solang das x klein bleibt, ohne in
> ein Stack Overflow zu kommen, oder?

Ja, klar. Der Stack ist nach Rückkehr aus der Funktion im selben Zustand 
wie vor ihrem Aufruf. Wenn die Funktion aber sich  selber aufruft, 
braucht jede Aufrufebene etwas Stack, so dass der bei zu großer Tiefe 
nicht mehr ausreicht (Sofern die Compiler-Optimierung das nicht 
auflöst).

Autor: Dr. Sommer (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
schlaubi schrieb:
>> ... eigentlich sollte doch jeder in der Lage sein, eine Rekursion in
>> eine "while"-Schleife umzuwandeln - oder auch umgekehrt, wenn nötig.
>
> Dann zeig das mal fuer das Ackermannsche Funktional,
> Herr Universitaeter!

Wenn man while-Schleifen und beliebig viel Speicher zur Verfügung hat 
geht das :-) Das verlagert aber letztendlich nur den Stack auf den Heap 
(oder welche "unendliche" Datenstruktur man jetzt hat). Das kann je nach 
Anwendung sinnvoll sein, aber Rekursion grundsätzlich zu verteufeln 
halte ich für falsch, vor allem wenn Compiler das so schön wegoptimieren 
können.

Autor: Bernd B. (microwave-designer)
Datum:

Bewertung
-1 lesenswert
nicht lesenswert
schlaubi schrieb:
> Dann zeig das mal fuer das Ackermannsche Funktional,

Hallo Schlaubi, wenn Du genau zuhörst, stellst du sicher fest, dass Dein 
Vergleich hinkt!

Youtube-Video "Ackermannfunktion"

Oder in Worten:
"Die Ackermannfunktion ist eine 1926 von Wilhelm Ackermann gefundene, 
extrem schnell wachsende mathematische Funktion, mit deren Hilfe in der 
theoretischen Informatik Grenzen von Computer- und Berechnungsmodellen 
aufgezeigt werden können...."

Dieses Verfahren zeigt die Grenzen auf! Nun liegt es an Dir, lieber 
Schlaubi, zu zeigen, dass bei einem rekursiven Aufruf die Grenzen nicht 
vorhanden sind!

Gruß

Bernd

Autor: Dr. Sommer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bernd B. schrieb:
> Dieses Verfahren zeigt die Grenzen auf! Nun liegt es an Dir, lieber
> Schlaubi, zu zeigen, dass bei einem rekursiven Aufruf die Grenzen nicht
> vorhanden sind!

Die Definition der Ackermann-Funktion ist eine Rekursion mit 
unbegrenzter aber endlicher Tiefe. Somit kann sie logischerweise durch 
Rekursion berechnet werden - aber eben nicht durch Schleifen mit 
fixer(!) Iterations-Zahl ("Loop-Programme").

Autor: Bernd B. (microwave-designer)
Datum:

Bewertung
-1 lesenswert
nicht lesenswert
Dr. Sommer schrieb:
> Wenn man while-Schleifen und beliebig viel Speicher zur Verfügung hat

Hallo Doc, eine Möglichkeit bei der Rekursion den Stack nicht weiter 
anwachsen zu lassen, wäre die die Wiederverwendung von Variablen in der 
Schachtelung. Also wäre Variable "a-strich-n" aus Rekursionstiefe "n" im 
nächsten Rekursionsschritt"n+1" wiederzuverwenden. Die Variable 
"a-strich-n+1" benutzt dann die selbe Speicherzelle (egal ob Heap oder 
Stack). Bei der Fakultät ist ja das Ergebnis beim Erreichen der 
maximalen Rekursionstiefe erreicht und wird an alle höheren Ebenen als 
Ergebnis zurück gegeben oder bei Wiederverwendung einfach so belassen. 
Nun ist es aus meiner Sicht aber so, dass sich die erste Rekursion von 
den weiteren Schachtelungen unterscheidet, da ja erst einmal Speicher 
für das Ergebnis reserviert werden muss. Damit entfällt bei der 
Verarbeitung entweder OP-Code auf die "if"-Bearbeitung, oder man 
reserviert den Speicher bereits vor dem ersten Aufruf. Dies könnte 
wahlweise auf Stack oder Heap oder sogar in einem Register erfolgen. 
Dies zeigt, dass man mit 2 Bytes nicht auskommt - unabhängig ob 
8-bitter, 16-bitter oder 32-bitter. Vergessen wir auch einmal die 
Statusregister und "pending" Interrupts.

Peter D. schrieb:
> Der Stackverbrauch ist also 2 Bytes für den Call.

Selbst wenn ich aus meiner Sicht mit jedem Rekursionsschritt die 
Rückkehradresse auf die selbe Speicherzelle im Stack lege, ich benötige 
dann nur ein "return" zur Rückkehr aus der gesamten Rekursionstiefe, bin 
ich mir nicht sicher was passiert, wenn während der 
Rekursionsbearbeitung  eine Interrupt-Routine aufgerufen und 
abgearbeitet wird. Auch erliegt man hier einer Täuschung, da die 
Aufwände für Speicherplatz nach außen, außerhalb der Rekursion verlegt 
werden.

Wer der bisher beschriebenen Überlegung gefolgt ist sollte einmal 
versuchen dieses Verhalten in eine allgemein gültige Strategie oder 
Anweisung eines Compilers zu formulieren. Dieses Verfahren sollte ja 
nicht nur für den Einzelfall der Berechnung einer Fakultät nach den oben 
benannten Randbedingungen funktionieren.

Ich sehe da zwar Potential (DE will ja KI stärken), aber ich bezweifle, 
dass heute verfügbare Compiler dieses Problem mit einer Handvoll 
Speicherzellen allgemein gültig löst.

Fruitful comments welcome!

Bernd

Autor: Dr. Sommer (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Bernd B. schrieb:
> Hallo Doc, eine Möglichkeit bei der Rekursion den Stack nicht weiter
> anwachsen zu lassen, wäre die die Wiederverwendung von Variablen in der
> Schachtelung.

Das geht eben nur, wenn nach der Rückkehr des verschachtelten Aufrufs 
keine Anweisungen mehr kommen, welche die Werte von "a-strich-n" nochmal 
brauchen. Bei der Fakultät geht das, bei der Ackermann-Funktion nicht.

Bernd B. schrieb:
> oder man
> reserviert den Speicher bereits vor dem ersten Aufruf.
Das ist normalerweise das was passiert. Der "normale" Aufruf von "außen" 
reserviert das Stack-Frame, und das wird bei der Rekursion recycled.

Bernd B. schrieb:
> Dies zeigt, dass man mit 2 Bytes nicht auskommt - unabhängig ob
> 8-bitter, 16-bitter oder 32-bitter.

Beim ARM braucht man sogar 0 Bytes auf dem Stack dank Link-Register.

Bernd B. schrieb:
> bin
> ich mir nicht sicher was passiert, wenn während der
> Rekursionsbearbeitung  eine Interrupt-Routine aufgerufen und
> abgearbeitet wird.
Nichts besonderes, das funktioniert ganz normal.

Bernd B. schrieb:
> Wer der bisher beschriebenen Überlegung gefolgt ist sollte einmal
> versuchen dieses Verhalten in eine allgemein gültige Strategie oder
> Anweisung eines Compilers zu formulieren.
Wenn der rekursive Aufruf das wirklich letzte in der Funktion ist, 
ersetze die Aufruf-Instruktion (welche die Rücksprungadresse sichert) 
durch einen simplen Sprung, und deallokiere vorher das Stack-Frame (oder 
belasse das Frame, und springe hinter die Allokation).

Bernd B. schrieb:
> Ich sehe da zwar Potential (DE will ja KI stärken), aber ich bezweifle,
> dass heute verfügbare Compiler dieses Problem mit einer Handvoll
> Speicherzellen allgemein gültig löst.
Das ist alles ein alter Hut und hat mit KI nix zu tun.

Hier mal konkret das, was der GCC so macht:

Diese angepasste Fakultäts-Funktion hat den rekursiven Aufruf als letzte 
Anweisung und führt das Ergebnis im "collect"-Parameter mit:
unsigned int fakultaet(unsigned int x, unsigned int collect) __attribute__ ((noinline));
unsigned int fakultaet(unsigned int x, unsigned int collect) {
  if(x > 1) 
  {
    return fakultaet(x-1, x * collect);
  }
  else 
  {
    return collect;
  }
}

unsigned int test () {
  return fakultaet (5, 1) * 2;
}
Das "noinline"-Attribute ist nötig, damit der Aufruf nicht komplett vom 
Compiler zu einer Konstante wegoptimiert wird. Das "*2" wird 
hinzugefügt, damit der Compiler in test() nicht auch eine Tail-Recursion 
einfügt (so schlau ist der). Das Ergebnis auf AMD64 ist:
0000000000000000 <fakultaet>:
   0:  89 f0                  mov    %esi,%eax
   2:  83 ff 01               cmp    $0x1,%edi
   5:  76 14                  jbe    1b <fakultaet+0x1b>
   7:  66 0f 1f 84 00 00 00   nopw   0x0(%rax,%rax,1)
   e:  00 00 
  10:  0f af c7               imul   %edi,%eax
  13:  83 ef 01               sub    $0x1,%edi
  16:  83 ff 01               cmp    $0x1,%edi
  19:  75 f5                  jne    10 <fakultaet+0x10>
  1b:  c3                     retq   
  1c:  0f 1f 40 00            nopl   0x0(%rax)

0000000000000020 <test>:
  20:  be 01 00 00 00         mov    $0x1,%esi
  25:  bf 05 00 00 00         mov    $0x5,%edi
  2a:  e8 00 00 00 00         callq  2f <test+0xf>
  2f:  01 c0                  add    %eax,%eax
  31:  c3                     retq

Man sieht, dass der Aufrufer (test) den Speicher anfordert (callq 
speichert die Rücksprungadresse auf dem Stack). Innerhalb von fakultaet 
baut der Compiler eine einfache Iteration komplett ohne irgendwelche 
Stack-Zugriffe. Der rekursive Aufruf wird durch einen Sprung in die 
Funktion selbst ersetzt. Der Speicher wird 1x nach Ende der Rekursion 
wieder freigegeben durch das "retq".

Noch schöner sieht das auf ARM aus:
00000000 <fakultaet>:
   0:  e3500001   cmp  r0, #1
   4:  9a000003   bls  18 <fakultaet+0x18>
   8:  e0010190   mul  r1, r0, r1
   c:  e2400001   sub  r0, r0, #1
  10:  e3500001   cmp  r0, #1
  14:  1afffffb   bne  8 <fakultaet+0x8>
  18:  e1a00001   mov  r0, r1
  1c:  e12fff1e   bx  lr

00000020 <test>:
  20:  e92d4010   push  {r4, lr}
  24:  e3a01001   mov  r1, #1
  28:  e3a00005   mov  r0, #5
  2c:  ebfffffe   bl  0 <fakultaet>
  30:  e8bd4010   pop  {r4, lr}
  34:  e1a00080   lsl  r0, r0, #1
  38:  e12fff1e   bx  lr
Die fakultaet-Funktion greift überhaupt nicht auf den Stack zu. Der 
Compiler konstruiert wieder eine einfache Schleife. Der Rücksprung 
erfolgt über das Link-Register.
Die test()-Funktion hingegen wird hier suboptimal umgesetzt - der 
Compiler sichert unnötigerweise das r4-Register auf dem Stack.

Die Rekursion lässt sich hier also wunderbar für die Fakultät nutzen, 
ohne dass hier ein Stack Overflow eintreten kann.

Autor: Bernd B. (microwave-designer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Doc,

ich sehe, Du hast Teile meiner Ausführung verstanden und mit eigenen 
Worten wiedergegeben.

Gruß

Bernd

Autor: Peter D. (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bernd B. schrieb:
> bin
> ich mir nicht sicher was passiert, wenn während der
> Rekursionsbearbeitung  eine Interrupt-Routine aufgerufen und
> abgearbeitet wird.

Es passiert einfach nichts.
Es ist allein Aufgabe des Compilers, daß ein Interrupt keinen Schaden 
anrichtet. Ein Interrupthandler muß alle verwendeten Register sichern 
und wiederherstellen.

Autor: Dr. Sommer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bernd B. schrieb:
> ich sehe, Du hast Teile meiner Ausführung verstanden und mit eigenen
> Worten wiedergegeben.

Ich hatte den Eindruck, dass du nicht verstanden hattest, dass/wie 
Compiler das machen und es dir daher demonstriert.

Autor: Bernd B. (microwave-designer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Doc,

so ist das mit der Kommunikation im Forum. Sitzt man sich gegenüber, 
sieht man z.B. am Gesichtsausdruck, bereits während der "Transmission", 
wie die Signale empfangen werden.

Auch die Körperhaltung oder "zappeln" verrät einiges.

Smiley

Bernd

Autor: Bernd B. (microwave-designer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dr. Sommer schrieb:
> Bernd B. schrieb:
>> Ich sehe da zwar Potential (DE will ja KI stärken), aber ich bezweifle,
>> dass heute verfügbare Compiler dieses Problem mit einer Handvoll
>> Speicherzellen allgemein gültig löst.
> Das ist alles ein alter Hut und hat mit KI nix zu tun.

Doc, noch'ne Antwort. Ja, vieles ist alter Hut. Z.B. vieles aus 
Industrie 4.0 ist alter Hut.

Spannend finde ich, wenn man KI in die Rekursion einwirft oder 
umgekehrt. Ist es nicht so, dass man quasi mit jeder Zeiteinheit in eine 
neue Tiefe eintaucht und den Prozess so fortsetzt? Gut, man kann diesen 
Thread als Liste betrachten. Dennoch, die Entwicklung der Problemlösung 
und der Austausch untereinander ließe sich auch rekursiv betrachten. Mit 
jedem qualifizierten Beitrag, der an vorherige anknüpft tauchen wir doch 
tiefer ein. Das ist doch was Rekursion ausmacht.

Oder das Lernen im Leben (ich nehme indirekt Bezug auf die nachgebauten 
Menschen in China oder Japan) lässt sich doch auch als Tunnel oder 
Schlauch darstellen, an dessen Eingang alles einmal begann. Der 
Lernprozess kann als Baumstruktur oder Liste betrachtet werden. Jedoch 
entfallen viele sobald man sich in die Tiefen einer Rekursion stürzt. 
Alle nicht benötigten Verzweigungen befinden sich dann außerhalb des 
Tunnels.

Man könnte hier vielleicht anknüpfen und einen SciFi-Roman schreiben.

Fruitful ...

Bernd

Autor: schlaubi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich habe Teilbereiche des Ackermannschen Funktionals schon
zu Z80-Zeiten mit 3 kByte RAM berechnet.

Um die Rekursion wirkungsvoll zu begrenzen, werden
Werte nicht auf den Stapelspeicher geschrieben, sondern
vor dem Verlassen der Rekursionsebene einfach wieder
hergestellt. Z.B. wird ein inkrementierter Wert vor dem
Verlassen wieder Dekrementiert...u.s.w.u.s.f.

Autor: Bernd B. (microwave-designer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dr. Sommer schrieb:
> Bernd B. schrieb:
>> Ich sehe da zwar Potential (DE will ja KI stärken), aber ich bezweifle,
>> dass heute verfügbare Compiler dieses Problem mit einer Handvoll
>> Speicherzellen allgemein gültig löst.
> Das ist alles ein alter Hut und hat mit KI nix zu tun.

Nachtrag: "Zur KI -> Widerspruch Euer Ehren!"... schade, etwa ein 
viertel Jahrhundert zu spät (das Original-Paper)...

A Formula for Intelligence: The Recursive Paradigm - August 6, 2001 by 
Ray Kurzweil
An explanation of the recursive approach to artificial intelligence, 
written for “The Futurecast,” a monthly column in the Library Journal.

http://www.kurzweilai.net/a-formula-for-intelligence-the-recursive-paradigm

So, den SciFi-Roman können wir vergessen...

Gruß ins Forum

Bernd

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.

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