Rekursion

[Schneider]

Hallo,

ich habe rekursive Funktion geschrieben, um einen Pythagorasbaum darzustellen. Hier mal kurz eine einfache Variante der Funktion als Pseudocode notiert:

  
  
public void ZeichnePythagorasbaum(Punkt1, Punkt2, Tiefe) {  
 if (Tiefe >= 0) {  
 Tiefe--;  
 berechnePunkt3und4();  
 zeichnePolygon();  
 berechnePunktNeu();  
 ZeichnePythagorasbaum(PunktNeu, Punkt2, stufe);  
 ZeichnePythagorasbaum(Punkt4, PunktNeu, stufe);  
 }  
}  
  
ZeichnePythagorasbaum((200, 340), (270, 340),15);  
  

1.)Die Funktion wird aufgerufen
2.) weitere Eckpunkte werden berechnet
3.) Polygon wird gezeichnet
4.) neuer Punkt wird berechnet
5.) ZeichnePythagorasbaum() ruft sich wieder selbst auf

Was ich nicht verstehe: der zweite nun folgende Funktionsaufruf dürft doch nie stattfinden...? Oder gibt die Funktion ZeichnePythorasbaum() implizit etwas zurück, bevor sie sich selbst zum zweiten Mal aufruft....?

[Schneider]

muss natürlich
ZeichnePythagorasbaum(PunktNeu, Punkt2, Tiefe);
 ZeichnePythagorasbaum(Punkt4, PunktNeu, Tiefe);

heissen.

Und nochmal in blau:

Wenn ich diese Funktion wie oben konstruiert aufrufe (d.h. als einfache rekursive Funktion ohne Thread-Funktionalität etc) friert bei einer Tiefe von über 16 meine Entwicklungsumgebung ein (Intel-Laptop, OS Open-Suse, Entwicklungsumgebung Processing, JavaCode). Scheinbar ist der RAM voll. Nun kenne ich mich in Threadprogrammierung bzw. Java nicht gut aus. Gibt es grundsätzlich irgendwelche Möglichkeiten, um höhere Tiefen zu erreichen? RAM leeren nach jedem Funktionsaufruf oder ähnliches?

Viele Grüße
Schneider

[dedlfix]

Hi!

public void ZeichnePythagorasbaum(Punkt1, Punkt2, Tiefe) {
if (Tiefe >= 0) {
Tiefe--;
[...]
ZeichnePythagorasbaum(PunktNeu, Punkt2, stufe);
ZeichnePythagorasbaum(Punkt4, PunktNeu, stufe);
}
}
ZeichnePythagorasbaum((200, 340), (270, 340),15);

Was ich nicht verstehe: der zweite nun folgende Funktionsaufruf dürft doch nie stattfinden...? Oder gibt die Funktion ZeichnePythorasbaum() implizit etwas zurück, bevor sie sich selbst zum zweiten Mal aufruft....?

Sie gibt eben nichts zurück. Tiefe bleibt nach dem Dekrementieren unverändert für den Rest dieser Funktionsinkarnation. Wenn du mit 15 startest rufst du startest du beide Funktionsaufrufe mit jeweils 14.

Wenn ich diese Funktion wie oben konstruiert aufrufe ([...] friert bei einer Tiefe von über 16 meine Entwicklungsumgebung ein [...]. Scheinbar ist der RAM voll. Nun kenne ich mich in Threadprogrammierung bzw. Java nicht gut aus. Gibt es grundsätzlich irgendwelche Möglichkeiten, um höhere Tiefen zu erreichen? RAM leeren nach jedem Funktionsaufruf oder ähnliches?

Ein Funktionsaufruf ergibt zwei weitere Funktionsaufrufe, insgesamt 3. Je nach Tiefe geht das in Zweierpotenzen weiter: 1 => 2 => 4 => 8 => 16 => 32 => 64 => 128 => 256 ... Es fängt klein an, aber es steigert sich dann stark. Im RAM ist sicher noch genügend Platz aber entweder läuft dir der Stack über, oder die Berechnungen dauern einfach zu lange.

Lo!

[Schneider]

Hallo

Was ich nicht verstehe: der zweite nun folgende Funktionsaufruf dürft doch nie stattfinden...? Oder gibt die Funktion ZeichnePythorasbaum() implizit etwas zurück, bevor sie sich selbst zum zweiten Mal aufruft....?

Sie gibt eben nichts zurück. Tiefe bleibt nach dem Dekrementieren unverändert für den Rest dieser Funktionsinkarnation. Wenn du mit 15 startest rufst du startest du beide Funktionsaufrufe mit jeweils 14.

Das verstehe ich schon. Was ich nicht verstehe, ich stehe gerade auf dem Schlauch:

  
function recfun($text,$tiefe){  
$tiefe++;  
if($tiefe>100)exit;  
  
$format = "Text %s, Tiefe %s \n";  
printf($format, $text, $tiefe);  
  
recfun("machdies",$tiefe);  
recfun("machdas",$tiefe);  
}  
  
recfun("machma",0)  

Ich hätte jetzt erwartet, dass recfun niemals mit "machdas" aufgerufen wird, weil sich die Funktion ja immer erst mit "machdies" erneut aufruft.
Dieses kleine Testscript bestätigt zumal meine Vermutung. Warum ist das so? Was ist der Unterschied von PHP zu JAVA hinslichtlich dieser Unterscheidung?

[dedlfix]

Hi!

if($tiefe>100)exit;
Ich hätte jetzt erwartet, dass recfun niemals mit "machdas" aufgerufen wird, weil sich die Funktion ja immer erst mit "machdies" erneut aufruft.

exit beendet das Script. Nimm return.

Lo!

[Schneider]

Hi,

hab das mal gemacht mit einer Tiefe von 5

Text machma, Tiefe 1
Text machdies, Tiefe 2
Text machdies, Tiefe 3
Text machdies, Tiefe 4
Text machdies, Tiefe 5
Text machdas, Tiefe 5
Text machdas, Tiefe 4
Text machdies, Tiefe 5
Text machdas, Tiefe 5
Text machdas, Tiefe 3
Text machdies, Tiefe 4
Text machdies, Tiefe 5
Text machdas, Tiefe 5
Text machdas, Tiefe 4
Text machdies, Tiefe 5
Text machdas, Tiefe 5
Text machdas, Tiefe 2
Text machdies, Tiefe 3
Text machdies, Tiefe 4
Text machdies, Tiefe 5
Text machdas, Tiefe 5
Text machdas, Tiefe 4
Text machdies, Tiefe 5
Text machdas, Tiefe 5
Text machdas, Tiefe 3
Text machdies, Tiefe 4
Text machdies, Tiefe 5
Text machdas, Tiefe 5
Text machdas, Tiefe 4
Text machdies, Tiefe 5
Text machdas, Tiefe 5

Kann das so stimmen?

[dedlfix]

Hi!

hab das mal gemacht mit einer Tiefe von 5
Kann das so stimmen?

Ja, es sind genau 31 Zeilen, 1 + 2 + 4 + 8 + 16.

Lo!