Moin,
wenn ich eine Funktion habe die rekursiv arbeitet z.B. um die Fakultät
zu berechnen:
1
intfakultaet(intx){
2
if(x>1)
3
{
4
returnx*fakultaet(x-1);
5
}
6
else
7
{
8
return1;
9
}
10
}
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
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.
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.
> 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.
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.
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.
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ß.
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.
... 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?
1
function fakultaet(const i:integer):integer;
2
var fak:integer;
3
begin
4
{ error treatment outside this function }
5
fak:=1;
6
while i>1
7
begin
8
fak:=fak*i;
9
i:=i-1
10
end;
11
fakultaet:=fak
12
end;
Warnung: ... kann Fehler enthalten - nicht kompiliert!
Smiley
Bernd
> ... 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!
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).
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.
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!
https://www.youtube.com/watch?v=NnZVpiKZpkM
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
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").
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
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:
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:
1
0000000000000000 <fakultaet>:
2
0: 89 f0 mov %esi,%eax
3
2: 83 ff 01 cmp $0x1,%edi
4
5: 76 14 jbe 1b <fakultaet+0x1b>
5
7: 66 0f 1f 84 00 00 00 nopw 0x0(%rax,%rax,1)
6
e: 00 00
7
10: 0f af c7 imul %edi,%eax
8
13: 83 ef 01 sub $0x1,%edi
9
16: 83 ff 01 cmp $0x1,%edi
10
19: 75 f5 jne 10 <fakultaet+0x10>
11
1b: c3 retq
12
1c: 0f 1f 40 00 nopl 0x0(%rax)
13
14
0000000000000020 <test>:
15
20: be 01 00 00 00 mov $0x1,%esi
16
25: bf 05 00 00 00 mov $0x5,%edi
17
2a: e8 00 00 00 00 callq 2f <test+0xf>
18
2f: 01 c0 add %eax,%eax
19
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:
1
00000000 <fakultaet>:
2
0: e3500001 cmp r0, #1
3
4: 9a000003 bls 18 <fakultaet+0x18>
4
8: e0010190 mul r1, r0, r1
5
c: e2400001 sub r0, r0, #1
6
10: e3500001 cmp r0, #1
7
14: 1afffffb bne 8 <fakultaet+0x8>
8
18: e1a00001 mov r0, r1
9
1c: e12fff1e bx lr
10
11
00000020 <test>:
12
20: e92d4010 push {r4, lr}
13
24: e3a01001 mov r1, #1
14
28: e3a00005 mov r0, #5
15
2c: ebfffffe bl 0 <fakultaet>
16
30: e8bd4010 pop {r4, lr}
17
34: e1a00080 lsl r0, r0, #1
18
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.
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.
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.
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
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
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.
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
Thread beobachten
Seitenaufteilung abschalten