Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Fakultaet- rekursiv oder iterativ?
u-schas - Mi 08.06.05 17:55
Titel: Fakultaet- rekursiv oder iterativ?
Ich habe zwei Möglichkeiten wie ich eine Fakultaet programmieren kann, rekursiv oder iterativ. Die rekursive Art ruft sich immer wieder selbst auf und könnte doch ab einen gewissen Grad zum Absturz des Programmes führen, oder? Meine Frage ist wie weit kann ich mit der rekurisven Formel gehen, damit mein Programm noch läuft?
F34r0fTh3D4rk - Mi 08.06.05 18:18
ähm du musst da sowieso ne abfrage einbauen, und dann sollte es nicht abstürzen :!:
Hier die Function
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
| Function Fakultaet(Zahl : integer): Integer;
begin
If Zahl = 0 then
result := 1
else
result := Zahl * Fakultaet(Zahl - 1);
end; |
hatte das
result := 1 vergessen :roll:
Stefan.Buchholtz - Mi 08.06.05 18:28
Hier würde ich aber die iterative Lösung vorziehen - die ist ja hier trivial zu implementieren:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
| function Fakultaet(Zahl: integer): integer;
var
i : Integer;
begin
Result := 1;
for i := 2 to Zahl do
begin
Result := Result * i;
end;
end; |
Es gibt natürlich Algorithmen - Quicksort z.B. - wo man sich für eine iterative Implementation einen abbricht, aber das ist ja hier nicht der Fall.
Um deine ursprüngliche Frage zu beantworten: Die Aufruftiefe ist normalerweise unkritisch. Windows kann den Stack so weit vergrößern, dass sich eine funktion hunderte von Malen selbst aufrufen kann, bevor du einen Stack-Überlauf bekommst. Viel eher brauchst du bei der Fakultät einen Datentyp, der größere Zahlen darstellen kann als es mit Integern oder selbst Int64 möglich ist - an diese Grenze stösst du viel schneller als an die maximale Rekursionstiefe.
Stefan
Gausi - Mi 08.06.05 18:30
Wenn du allerdings meinst, dass der Stack irgendwann überläuft, dann kann ich dich beruhigen. Das wird da nicht passieren. Zumindest nicht mit den Standard-Datentypen Integer oder Int64. Habe das spaßeshalber mal mit Extended probiert, und auch da ist das kein Problem. Allerdings ist bei 1754 Schluss, danach kommt ein Gleitkomma-Überlauf. Aber 1.9*10^4930 ist auch schon ne ziemlich große Zahl...
raziel - Mi 08.06.05 18:37
:welcome: u-schas,
 F34r0fTh3D4rk hat folgendes geschrieben: |
| ähm du musst da sowieso ne abfrage einbauen, und dann sollte es nicht abstürzen :!: |
Die Abfrage ist, glaub ich, nicht u-schas Problem. Denn irgendwo hat er Recht. Ein Integer belegt (momentan) 4 Byte. Dann kommt noch die Rücksprungadresse hinzu. Um die Fakultät von 2-Million zu berechnen sind gerade mal knapp über 15kB an Stack von Nöten. Wenn man bedenkt, dass man hier schon längst zig Overflows erzeugt hat, dürfte die Rekursivität keine größeren Probleme bereiten. Eher schon die Zeit, die die Funktionsaufrufe benötigen, wobei hier wohl aus zeitlichen Gründen die Iterative Methode besser ist.
Gruß,
raziel
u-schas - Mi 08.06.05 21:28
Ahhhh, also bekomme ich keine Problem mit einem Absturz, sondern Probleme mit der Variablen Integer. Das ist genau das, was ich wissen wollte, vielen Dank.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!