Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Rekursion, ein paar zehntausend Mal?


monster - So 26.11.06 22:01
Titel: Rekursion, ein paar zehntausend Mal?
Hi, ich hab ein Problem.
Ich hab ne Methode geschrieben mit der man Flächen ausfüllen kann. Ich dachte mir: Hey, das mach ich rekursiv, wirdn Klacks! Wars auch und die ersten Rechtecke waren schnell gefüllt, aber als ich versucht hab größere Flächen zu füllen, stürzte das Programm sofort ab, es gab nichtmal eine Fehlermeldung.
Ich hab herausgefunden, dass Rechtecke bis zu einem Flächeninhalt von 47499 Pixeln gefüllt werden, alles darüber... Gibt es da Beschränkungen, was sich selbst aufrufende Funktionen angeht? Hier mein code:


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
// Nach außen auftretende, komfortablere Methode
procedure TQxGCore.FloodFill(p: TQxPoint);
begin
  if (p.x < 0or (p.x >= fsystem.screen.w) or
     (p.y < 0or (p.y >= fsystem.screen.h) then exit;
  if fsystem.status <> stRunning then exit;
  HlpFloodFill(p.x, p.y, getPixel(p.x, p.y));
end;

// Rekursive Hilfsmethode
procedure TQxGCore.HlpFloodFill(x, y, c: cardinal);
begin
  setPixel(x, y, getR(brush.color), getG(brush.color), getB(brush.color));
  if x > 0 then
    if getPixel(x - 1, y) = c then HlpFloodFill(x - 1, y, c);
  if x < fsystem.width - 1 then
    if getPixel(x + 1, y) = c then HlpFloodFill(x + 1, y, c);
  if y > 0 then
    if getPixel(x, y - 1) = c then HlpFloodFill(x, y - 1, c);
  if y < fsystem.height - 1 then
    if getPixel(x, y + 1) = c then HlpFloodFill(x, y + 1, c);
end;


Hilfe! (Bitte)


Bernhard Geyer - So 26.11.06 22:17
Titel: Re: Rekursion, ein paar zehntausend Mal?
user profile iconmonster hat folgendes geschrieben:
Gibt es da Beschränkungen, was sich selbst aufrufende Funktionen angeht? Hier

Ja. Dein eingestellter Stack-Frame für deine Anwendung (Unter Projektoptionen zu finden).
Ich würde mir aber überlegen ob du das nicht die Rekursion in eine Schleife umwandelst.


monster - So 26.11.06 22:26
Titel: Re: Rekursion, ein paar zehntausend Mal?
user profile iconBernhard Geyer hat folgendes geschrieben:
[...]
Ich würde mir aber überlegen ob du das nicht die Rekursion in eine Schleife umwandelst.

Hatte ich kurz dran gedacht, aber ich weiß nicht ob ich das übers Herz bringe. Der code ist so simpel, so elegant, grazil, effizient, göttlich, perfekt... *schnief* Es ist als würde ich meinen (ungeborenen) Sohn umbringen.

Ich fürchte aber es geht nicht anders. Danke für die prompte Antwort.


uall@ogc - So 26.11.06 23:00

Gute Füllalgorithmen benutzen keine Rekursion.