# Rekursion



## Guest (5. Jun 2008)

Hallo,

hänge gerade an einer rekursiven Aufgabe für ein Applet.

Es soll rekursiv ein Kreuz ausgegeben werden, an dessen Enden wiederum ein Kreuz ist usw.
Breite und Höhe der neuen Kreuze sind 1/3, Mittelpunkt bei 3/4 der Schenkellänge des ursprünglichen Kreuzes.
Hab mal ein Bild hochgeladen damit man besser erkennt was ich meine...

Kann mir jemand beim Ansatz dafür helfen? Muss ich das über n Turtel machen?
Dachte zuerst an nen rekursiven Aufruf von drawLine aber konnte das nicht wirklich umsetzten weil ich ja anfangs an 4 Ecken, dann an 16, usw. Ecken zeichnen müsste...

Bitte helft mir auf die Sprünge!
Bitte keine kompletten Lösungs-Code - nur eine Spur zum Ziel   :wink: 

Danke!






direkter Link zu dem Bild (falls es Anzeigeprobleme gibt):  http://www.bilder-hochladen.net/files/6x63-1-jpg.html


----------



## SlaterB (5. Jun 2008)

> weil ich ja anfangs an 4 Ecken, dann an 16, usw. Ecken zeichnen 

die Rekursion hilft dir genau diese Probleme zu vermeiden,
du malst ein Kreuz, berechnest die 4 Punkte und rufst die Rekursion für jeden dieser Punkte mit kleinerer Seitenlänge auf, 

noch an Abbruchbedingung denken,
fertig


----------



## Guest (5. Jun 2008)

Also doch!

Ok, dann habe ich aber das Problem mit dem Aufruf von paint:


```
public void main(String[] args){
		paint (50, 100, null);
	}
	public void paint (int x, int y, Graphics g){
		g.drawLine(x, y, x+y, y);
		g.drawLine(y, x, y, x+y);
	}
```

damit wollte ich jetzt erstmal austesten.

Die Rekursion muss ja schon die paint-Methode sein? Aber irgendwie meckert mein Compiler dass er paint static haben will und wenn ich dem nachkomme zeichnet paint nicht mehr...


----------



## SlaterB (5. Jun 2008)

hat es denn vorher gezeichnet? wie überhaupt wenn du es nie ausprobieren konntest ohne main?
was soll übehaupt g malen wenn du doch g=null übergibst?

schon mal was von Swing/ AWT, Fenster, JFrame usw gehört?
du kannst nicht einfach in die Luft zeichnen


----------



## Guest (5. Jun 2008)

klar...


```
import java.applet.Applet;
import java.awt.Graphics;

public class Teil_b extends Applet {
	
	public void main(String[] args){
		paint (50, 100, null);
	}
	public void paint (int x, int y, Graphics g){
		g.drawLine(x, y, x+y, y);
		g.drawLine(y, x, y, x+y);
	}
}
```

dachte mir ich lass das ma hier weg weils ja eigentlich nich wirklich relevant ist, da immer gleich...


```
import java.applet.Applet;
import java.awt.Graphics;

public class Teil_b extends Applet {

	public void paint (Graphics g){
int x=50, y=100;
		g.drawLine(x, y, x+y, y);
		g.drawLine(y, x, y, x+y);
	}
}
```
zeichnet!


----------



## SlaterB (5. Jun 2008)

die Signatur von
public void paint (Graphics g){ 
}
darst du nicht verändern, keine zusäztlichen Parameter einfügen,
lies dir mal ein Kapitel zum Painting in AWT/ Swing durch

null zu übergeben und dann mit g irgendwas zu machen kann von Natur aus nur zu einer NullPointerException führen,
ein paar Regeln muss man beim Programmieren schon beachten


----------



## Guest (5. Jun 2008)

:shock: oha, ok...

ja aber wie mach ich dann einen aufruf von paint?
Ich muss doch paint rekursiv aufrufen, oder?


----------



## SlaterB (5. Jun 2008)

paint bleibt wie es ist und sorgt dafür dass du ein schönes tolles nicht-null-g von der Swing-Grafik-Routine bekommst,

wenn du das hast, dann kannst du beliebiges damit machen,
dann kannst du eine andere Operation, z.B. paintRec(..) rekursiv aufrufen


----------



## Guest (5. Jun 2008)

sorry, aber ich steh irgendwie auf dem schlauch...

lach mich aus - aber du meinst ich soll paint leer lassen und danach n paintRec?!


```
import java.applet.Applet;
import java.awt.Graphics;

public class Teil_b extends Applet {

	public void paint (Graphics g){
	}
	
	public void paintRec(int x, int y){
		g.drawLine(x, y, x+y, y);
		g.drawLine(y, x, y, x+y);
	}
}
```

Ich verstehs nich...


----------



## Guest (5. Jun 2008)

ah, der Knoten ist geplatzt...

*sich auf die stirn haut*

du meintest was in der Art:


```
import java.applet.Applet;
import java.awt.Graphics;


public class Teil_b extends Applet {

	public void paint (Graphics g){
		paintRec(50,100, g);
	}
	
	public void paintRec (int x, int y, Graphics g){
		g.drawLine(x, y, x+y, y);
		g.drawLine(y, x, y, x+y);
	}
}
```

ok, jetzt ist klar... muss ich nurnoch die passende Rekursion finden - danke schonmal!


----------



## SlaterB (5. Jun 2008)

ich meine paint nicht verändern (weder Namen noch Parameter) und von dort aus (fast alles) machen was dir lustig ist

```
import java.applet.Applet;
import java.awt.Graphics;

public class Teil_b extends Applet {

	public void paint (Graphics g){
	    paintRec();                   
	    paintRec3();
	    paintMond();
	}
	
	public void paintRec(int x, int y){
 	    paintMond();
 	    paintXY();
 	    ...
	}

 	    .....
}
```

natürlich auch hier nich die Grundgesetze von Java außer acht lassen,
in paintRec kannst du nicht auf g malen, wenn g nicht als Parameter übergeben wurde,
meinen Code auch nur als grobes Beispiel ansehen, stimmt auch nicht ganz von den Parametern


gut nacht


edit: die Erkenntnis im Post vorher wurde erst später editiert, da passt mein Post nun nicht mehr so richtig


----------



## Guest (5. Jun 2008)

alles klar - vielen Dank!

Ich hoffe ich bekomme es nun hin... Hab jetzt zumindest mal einen brauchbaren Ansatz!


----------



## Marco13 (6. Jun 2008)

Bei Rekursion wird übrigens ein kompliziertes Problem schrittweise vereinfacht, und immer die Lösung des einfachen Problems für die Lösung des komplizierten Problems verwendet. Falls du das Prinzip der Rekursion inzwischen verstanden hast, ist alles in Ordnung. Andernfalls kannst du dir mal diesen Beitrag ansehen. :lol:


----------



## Guest (6. Jun 2008)

@marco - irgendwie funktioniert dein Link nicht (er verweist auf diese Seite)...

Ich bin jetzt mal so weit:

```
import java.applet.Applet;
import java.awt.Graphics;


public class Teil_b extends Applet {

	public void paint (Graphics g){
		kreuz(100, 100, 100, g);
	}
	
	public void kreuz(int x, int y, int l, Graphics g){
		g.drawLine(x, y, x-l, y);
		g.drawLine(x, y, x+l, y);
		g.drawLine(x, y, x, y-1);
		g.drawLine(x, y, x, y+1);
		l=l/3;
		
		if (l>1){
			kreuz(x-x*(3/4), y, l, g);
			kreuz(x+x*(3/4), y, l, g);
			kreuz(x, y-y*(3/4), l, g);
			kreuz(x, y+y*(3/4), l, g);
		}
	}
}
```

Im Prinzip müsste es doch so funktionieren...
Das Applet zeigt bei mir aber nur eine horizontale Linie bei der in der Mitte eine winzige (ca 4px lang) senkrechte Linie ist...
Wo liegt mein Fehler? Habe schon versucht den Code auf nem Platt Papier umzusetzen, und da klappt es auch...


----------



## Marco13 (6. Jun 2008)

Der Link in dem Beitrag verweist auf den Beitrag, in dem der Link steht. Überleg' mal scharf, warum :wink:

Sowas wie 
int xNeu = 100 * (3/4);
liefert xNeu==0, weil 3/4 mit ints (Ganzzahlen) berechnet wird, und dabei dann 0 rauskommt.

Mit sowas wie
int xNeu = (int)(100 * (3.0/4.0));
kommt das gewünschte xNeu==75 raus.

Die Rekursion selbst stimmt wohl noch nicht 100%ig, aber der Ansatz für die Rekursion ist schon richtig.


----------



## Marco13 (6. Jun 2008)

So als Nachtrag: Debug-Ausgaben helfen bei sowas:

```
public void kreuz(int x, int y, int l, Graphics g){
    System.out.println("Zeichne bei "+x+", "+y+" ein Kreuz der Größe "+l);
      g.drawLine(x, y, x-l, y); 
    ....
```
damit wäre dir der Fehler auch sofort aufgefallen.


----------



## SlaterB (6. Jun 2008)

du solltest deinen Code auch auf l (elllll) vs 1 (einssss) untersuchen,
selbstmörderisch, eine Variable so zu nennen


----------



## Marco13 (6. Jun 2008)

Genau, besser sind solche Namen wie i, î, í und ì :wink:


----------



## Guest (6. Jun 2008)

Marco13 hat gesagt.:
			
		

> Mit sowas wie
> int xNeu = (int)(100 * (3.0/4.0));
> kommt das gewünschte xNeu==75 raus.


ja aber ich will doch 0,75*x und nicht 75*x. Ok, klar, mit double würds gehn, aber drawLine nimmt nur int.



> Die Rekursion selbst stimmt wohl noch nicht 100%ig, aber der Ansatz für die Rekursion ist schon richtig.


Wo genau liegt noch der Fehler? Wenn ichs wie gesagt von Hand zeichne finde ich ihn nicht... Bitte einen Tipp!


Ok, das mit l und 1 ist verständlich.
Ich benutze Eclipse für das Programmieren, weiß aber nicht genau wie man da debugt. Habe früher schon ein bisschen C in MS VisualStudio programmiert, aber da war das debugging irgendwie leichter ...


```
import java.applet.Applet;
import java.awt.Graphics;


public class Teil_b extends Applet {

	public void paint (Graphics g){
		kreuz(50, 50, 40, g);
	}
	
	public void kreuz(int x, int y, int i, Graphics g){
		g.drawLine(x, y, x-i, y);
		g.drawLine(x, y, x+i, y);
		g.drawLine(x, y, x, y-1);
		g.drawLine(x, y, x, y+1);
		i=i/3;
		
		if (i>1){
			kreuz(x-(int)(x*(3/4)), y, i, g);
			kreuz(x+(int)(x*(3/4)), y, i, g);
			kreuz(x, y-(int)(y*(3/4)), i, g);
			kreuz(x, y+(int)(y*(3/4)), i, g);
		}
	}
}
```


----------



## SlaterB (6. Jun 2008)

g.drawLine(x, y, x-i, y); 
      g.drawLine(x, y, x+i, y); 
      g.drawLine(x, y, x, y-1); 
      g.drawLine(x, y, x, y+1); 

wieso hast du da teilweise 1 statt i?

> Wo genau liegt noch der Fehler? Wenn ichs wie gesagt von Hand zeichne finde ich ihn nicht... Bitte einen Tipp! 


quark, guck dir doch einfach an, was dein Programm malt und rechnet,
kannst doch per als Debug ausgeben,

du erhöhst deine Positionen von einer bestimmten Kooridnate aus,

100 * 1.75 ist mit 175 vielleicht noch ok, noch mal ein Schritt weiter ist dann aber 175 * 1.75 = über 300, das willst du bestimmt nicht

dazu kann man keine Tipps geben außer mal logisch über die Sache nachzudenken


----------



## Guest (6. Jun 2008)

:autsch: gut, das war also tötlich...

richtig - da muss ich erstmal nochmal drüber nachdenken.

Danke auf jedenfall schonmal so weit!


----------



## Marco13 (6. Jun 2008)

Anonymous hat gesagt.:
			
		

> Marco13 hat gesagt.:
> 
> 
> 
> ...


Schau nochmal genau was dort steht. Anders gesagt:
3/4 == 0
3.0/4.0 == 0.75


----------



## Guest (6. Jun 2008)

Ok, soweit so gut... 


```
import java.applet.Applet;
import java.awt.Graphics;


public class Teil_b extends Applet {

	public void paint (Graphics g){
		kreuz(60, 60, 60, g);
	}
	
	public void kreuz(int x, int y, int i, Graphics g){
		g.drawLine(x, y, x-i, y);
		g.drawLine(x, y, x+i, y);
		g.drawLine(x, y, x, y-i);
		g.drawLine(x, y, x, y+i);
		System.out.println("Zeichne bei "+x+", "+y+" ein Kreuz der Größe "+i); 
		i=i/3;
		if (i>1){
			kreuz(x-(int)(x*(3.0/4.0)), y, i, g);
			kreuz(x+(int)(x*(3.0/4.0)), y, i, g);
			kreuz(x, y-(int)(y*(3.0/4.0)), i, g);
			kreuz(x, y+(int)(y*(3.0/4.0)), i, g);
		}
	}
}
```

liefert mir jetzt:

Zeichne bei 60, 60 ein Kreuz der Größe 60
Zeichne bei 15, 60 ein Kreuz der Größe 20
Zeichne bei 4, 60 ein Kreuz der Größe 6
Zeichne bei 1, 60 ein Kreuz der Größe 2
Zeichne bei 7, 60 ein Kreuz der Größe 2
*Zeichne bei 4, 15 ein Kreuz der Größe 2
Zeichne bei 4, 105 ein Kreuz der Größe 2*
Zeichne bei 26, 60 ein Kreuz der Größe 6
Zeichne bei 7, 60 ein Kreuz der Größe 2
Zeichne bei 45, 60 ein Kreuz der Größe 2
Zeichne bei 26, 15 ein Kreuz der Größe 2
Zeichne bei 26, 105 ein Kreuz der Größe 2
Zeichne bei 15, 15 ein Kreuz der Größe 6
Zeichne bei 4, 15 ein Kreuz der Größe 2
Zeichne bei 26, 15 ein Kreuz der Größe 2
Zeichne bei 15, 4 ein Kreuz der Größe 2
Zeichne bei 15, 26 ein Kreuz der Größe 2
Zeichne bei 15, 105 ein Kreuz der Größe 6
Zeichne bei 4, 105 ein Kreuz der Größe 2
Zeichne bei 26, 105 ein Kreuz der Größe 2
Zeichne bei 15, 27 ein Kreuz der Größe 2
Zeichne bei 15, 183 ein Kreuz der Größe 2
Zeichne bei 105, 60 ein Kreuz der Größe 20
Zeichne bei 27, 60 ein Kreuz der Größe 6
Zeichne bei 7, 60 ein Kreuz der Größe 2
Zeichne bei 47, 60 ein Kreuz der Größe 2
Zeichne bei 27, 15 ein Kreuz der Größe 2
Zeichne bei 27, 105 ein Kreuz der Größe 2
Zeichne bei 183, 60 ein Kreuz der Größe 6
Zeichne bei 46, 60 ein Kreuz der Größe 2
Zeichne bei 320, 60 ein Kreuz der Größe 2
Zeichne bei 183, 15 ein Kreuz der Größe 2
Zeichne bei 183, 105 ein Kreuz der Größe 2
Zeichne bei 105, 15 ein Kreuz der Größe 6
Zeichne bei 27, 15 ein Kreuz der Größe 2
Zeichne bei 183, 15 ein Kreuz der Größe 2
Zeichne bei 105, 4 ein Kreuz der Größe 2
Zeichne bei 105, 26 ein Kreuz der Größe 2
Zeichne bei 105, 105 ein Kreuz der Größe 6
Zeichne bei 27, 105 ein Kreuz der Größe 2
Zeichne bei 183, 105 ein Kreuz der Größe 2
Zeichne bei 105, 27 ein Kreuz der Größe 2
Zeichne bei 105, 183 ein Kreuz der Größe 2
Zeichne bei 60, 15 ein Kreuz der Größe 20
Zeichne bei 15, 15 ein Kreuz der Größe 6
Zeichne bei 4, 15 ein Kreuz der Größe 2
Zeichne bei 26, 15 ein Kreuz der Größe 2
Zeichne bei 15, 4 ein Kreuz der Größe 2
Zeichne bei 15, 26 ein Kreuz der Größe 2
Zeichne bei 105, 15 ein Kreuz der Größe 6
Zeichne bei 27, 15 ein Kreuz der Größe 2
Zeichne bei 183, 15 ein Kreuz der Größe 2
Zeichne bei 105, 4 ein Kreuz der Größe 2
Zeichne bei 105, 26 ein Kreuz der Größe 2
Zeichne bei 60, 4 ein Kreuz der Größe 6
Zeichne bei 15, 4 ein Kreuz der Größe 2
Zeichne bei 105, 4 ein Kreuz der Größe 2
Zeichne bei 60, 1 ein Kreuz der Größe 2
Zeichne bei 60, 7 ein Kreuz der Größe 2
Zeichne bei 60, 26 ein Kreuz der Größe 6
Zeichne bei 15, 26 ein Kreuz der Größe 2
Zeichne bei 105, 26 ein Kreuz der Größe 2
Zeichne bei 60, 7 ein Kreuz der Größe 2
Zeichne bei 60, 45 ein Kreuz der Größe 2
Zeichne bei 60, 105 ein Kreuz der Größe 20
Zeichne bei 15, 105 ein Kreuz der Größe 6
Zeichne bei 4, 105 ein Kreuz der Größe 2
Zeichne bei 26, 105 ein Kreuz der Größe 2
Zeichne bei 15, 27 ein Kreuz der Größe 2
Zeichne bei 15, 183 ein Kreuz der Größe 2
Zeichne bei 105, 105 ein Kreuz der Größe 6
Zeichne bei 27, 105 ein Kreuz der Größe 2
Zeichne bei 183, 105 ein Kreuz der Größe 2
Zeichne bei 105, 27 ein Kreuz der Größe 2
Zeichne bei 105, 183 ein Kreuz der Größe 2
Zeichne bei 60, 27 ein Kreuz der Größe 6
Zeichne bei 15, 27 ein Kreuz der Größe 2
Zeichne bei 105, 27 ein Kreuz der Größe 2
Zeichne bei 60, 7 ein Kreuz der Größe 2
Zeichne bei 60, 47 ein Kreuz der Größe 2
Zeichne bei 60, 183 ein Kreuz der Größe 6
Zeichne bei 15, 183 ein Kreuz der Größe 2
Zeichne bei 105, 183 ein Kreuz der Größe 2
Zeichne bei 60, 46 ein Kreuz der Größe 2
Zeichne bei 60, 320 ein Kreuz der Größe 2

ich sehe, dass z.B. die fette Ausgabe abgefangen werden muss - aber ich hab absolut keine Idee wie ich das machen soll... Mit if/else? aber das wird doch dann endlos lang oder?!


----------



## SlaterB (6. Jun 2008)

schade dass du nicht bei den bekannten Zahlen von 100 aus geblieben ist,
aber mein Beispiel
100 -> 175 -> 306

findet sich auch in deinen Ausgaben:
60 -> 105 -> 183

immer noch gilt dass du Code wie
kreuz(x-(int)(x*(3.0/4.0)), y, i, g);
hast,

wieso hängt die Höhe deiner Verschiebung von x und y ab?

wenn du die linke Seite und rechte Seite deiner Figur anschaust:

```
|
        |
        |
a------------------b
        |
        |
        |
```
dann hat a vielleicht einen x-Wert von 15, bei b x = 105
jetzt kannst du die neuen Positionen doch nicht 
links x von a-75% = 4 
und rechts x von b+75% = 183 wählen

-----

die Verschiebung sollte nichts mit x/y zu tun haben, außer natürlich, dass du von x/y aus verschiebst,

zum Glück hängt die Länge der Linien l oder i nicht auch von x/y ab, das wäre ja krumm geworden..

-------
ich zeige dir nur nochmal etwas plastischer auf, was da passiert,
wenn du keine Fähigkeiten zum Durchdenken dieses Problems hast, dann gehts eben nicht


----------



## Guest (6. Jun 2008)

aaaaahhh! Hab den Wink mit dem Zaunpfahl verstanden :wink:
die Verschiebung hängt von der Länge ab. Klar! Steht ja sogar in der Aufgabe - ich Idiot!

Alles klar - jetzt funktionierts!
Vielen vielen Dank für die Tipps!!!


----------

