Rekursion in Schleifenkonstrukt wandeln

[Jay1980]

Servus,

ich habe da nun was rekursiv geloest - klappt auch gut, wenn man 'normale' Mengen an Eingabepunkten in die Methode jagt - ab rund 300 gehts dann aber los - Stack Overflow.

Ich habe etwas nachgelesen und die Lösungsidee die ich hatte, ist dass ich das Konstrukt in eine while-Schleife packe, dann sollte das Problem mit dem Stack gelöst sein.

Bevor ich mir nun da den Kopf zerbreche, kann mir ja einer kurz Rueckmeldung geben, ob er das ähnlich sieht oder ob er eine andere Lösung kennt und nutzen würde.

Hier mal die Methode (meiste sind Kommentare, keine Scheu mal runter zu scrollen):

	/**
	 * Methode nimmt den groessten Umkreis aus dem TreeSet und vergleicht dann 
	 * die Umkreise nach Skyum. Am Ende steht der kleinste Kreis fest.
	 * 
	 * @return
	 */
	private int findeUmkreis() 
	{
		//System.out.println("KleinsterKreis - findeUmkreis() - Start eines Laufs ...");
		
		// Debugging des TreeSets
		int i = 0;
		for ( Umkreis u : umkreisBaum)
		{
			System.out.println("Umkreis Nummer " + i + " mit a: " + u.a.toString() + " | b: " + u.b.toString() + " | c: " + u.c.toString() +" | wvw: " + u.winkelVergleichsWert + " ; mp: " + u.berechneUndGibUmkreisMittelpunkt().toString() + "; radius: " + u.berechneUndGibRadius());
			i++;
		}
		
		// greift das groesste Element und vergleicht dass es auch ein potentieller Kandidat ist
		Umkreis uTop = nimmGroesstenKreis(); // also groesster Kreis aus drei Punkten und somit ein Kandidat ob er alle fasst
		
		System.out.println();
		System.out.println("... uTop genommen, hier bei " +
				"a: " + uTop.a.xWert + "; " + uTop.a.yWert + " | " +
				"b: " + uTop.b.xWert + "; " + uTop.b.yWert + " | " +
				"c: " + uTop.c.xWert + "; " + uTop.c.yWert + " | " + 
				"uTop-winkelVergleichsWert: " + uTop.winkelVergleichsWert );
		System.out.println();
		
		// Winkel von U anschauen
		// wenn Winkel kleiner 90 Grad ist - da ist der Umkreis
		// TODO getter schreiben
		if ( uTop.winkelVergleichsWert > 0 ) // gleichbedeutend mit 'tatsaechlicher Winkel kleiner 90 Grad
		{
			// KUK gefunden
			
			// berechne notwendige Kennzahlen und lass zu Ende laufen
			radius = uTop.radius;
			mittelpunkt = uTop.berechneUndGibUmkreisMittelpunkt();
			//System.out.println();
			//System.out.println("KleinsterKreis - findeUmkreis() - KUK gefunden, winkelVergleichsWert uTop (a: " + uTop.a.xWert + "; " + uTop.a.yWert + "| b: " + uTop.b.xWert + "; " + uTop.b.yWert + "| c: " + uTop.c.xWert + "; " + uTop.c.yWert + ") ist " + uTop.winkelVergleichsWert + "; r: " + radius + "; mp: " + mittelpunkt.xWert + "; " + mittelpunkt.yWert );
			
		}
		else 
		{
			// Debugging
			//System.out.println();
			//System.out.println("KleinsterKreis - findeUmkreis() - noch kein KUK, finde neuen Kreiskandidaten ...");

			// Stelle Eckdaten des Punktearrays fest
			int n = punkteBehaelter.size();
			int posB = punkteBehaelter.indexOf(uTop.b);
			
			// Debugging
			//System.out.println("--> Eckdaten Punktebehaelter hat die Groesse " + n);
			//System.out.println("--> Stellplatz von Referenzpunkt (" + uTop.b.toString() + ") ist " + posB );
			
			// nimm zwei neue Kreise in das Set auf
			
			// TODO Eigenheiten Modulo-Operator siehe JavaInsel8 S. 119
			// Modulo gibt den Rest an, also bei n = 4 und posB = 8 ist posB % n = 0, da 8 / 4 = 2 Rest 0;
			// Modulo bei n = 4 und posB bei 3 gibt 3/4 = 0 R 3, also 3;
			// Modulo bei n = 4 und posB bei -3 gibt;
			// Modulo bei n = 4 und posB bei 1 gibt 1/4 = 0 R 1, also 1;
			// Modulo ist immer negativ, wenn der Dividend (also der Wert vor dem Operator das Vorzeichens des Restes festlegt)
			// Modulo bei n = 4 und posB bei -1, das kommt wenn posB an Stelle 1 steht, aber ich zwei zurueck soll:
			// -1 / 4 = 0 R -1 ( jetzt sucht Java die Stelle -1 im Behaelter und wird beim alten Punkt fuendig, das ist falsch) 
			
			// Zugriffsindex standardmaessig bestuecken
			int pMinusZweiStellplatz 	= ( posB - 2 ) % n;
			int pMinusEinsStellplatz 	= ( posB - 1 ) % n;
			
			int pPlusEinsStellplatz 	= ( posB + 1 ) % n;
			int pPlusZweiStellplatz 	= ( posB + 2 ) % n;
			
			// Ausnahmen abgreifen
			
			// Fall (test4.test) [geloest]: 
			// ArrayOutOfBounds, wenn posB kleiner als 2 ist bzw. wird, was soll also passieren,
			// wenn ich bei Index -1 auf das vorletzte zugreifen soll
			// n = 4, p ist auf 1, p-2 ist also -1, ist also ArrayOutOfBounds
			// Loesung waere Stelle 3, also n - Rest
			if (pMinusZweiStellplatz < 0 )
			{
				int pMinusZweiStellplatzAlt = pMinusZweiStellplatz; // Stellplatz ist etwa -1
				pMinusZweiStellplatz = n + pMinusZweiStellplatzAlt; // Stellplatz wird dann 4 + (-1), also 3
			}
			
			// Fall (random10.points), siehe Fall (test4.test)
			if (pMinusEinsStellplatz < 0 )
			{
				int pMinusEinsStellplatzAlt = pMinusEinsStellplatz; // Stellplatz ist etwa -1
				pMinusEinsStellplatz = n + pMinusEinsStellplatzAlt; // Stellplatz wird dann 4 + (-1), also 3
			}
			
			// Fall ( random5.test): 
			// gibt nur noch 3 Kreise im Set
			if ( umkreisBaum.size() < 4 )
			{
				//System.out.println("KleinsterKreis - findeUmkreis() - nur noch 3 Kreise im Set im Behaelter ...");
				
				// nimm uTop und schau dir den Winkel an
				if ( uTop.winkelVergleichsWert > 0) 
				{
					// Umkreis ist uTop im Dreierpaket
					radius = uTop.radius;
					mittelpunkt = uTop.berechneUndGibUmkreisMittelpunkt();
					//System.out.println();
					//System.out.println("KleinsterKreis - findeUmkreis() - KUK gefunden (Spezialfall 'nur noch drei Kreise im Set - Dreierpack'; winkelVergleichsWert uTop (a: " + uTop.a.xWert + "; " + uTop.a.yWert + "| b: " + uTop.b.xWert + "; " + uTop.b.yWert + "| c: " + uTop.c.xWert + "; " + uTop.c.yWert + ") ist " + uTop.winkelVergleichsWert + "; r: " + radius + "; mp: " + mittelpunkt.xWert + "; " + mittelpunkt.yWert );
					return 2;
				}
				else
				{
					// Umkreis ist uTop ohne Referenzpunkt
					
					// Mittelpunkt der Strecke berechnen das ist der Umkreismittelpunkt
					mittelpunkt = uTop.berechneUndGibUmkreisMittelpunktEinerStrecke();
					
					// Radius einer Strecke
					radius = uTop.berechneUndGibRadiusEinerStrecke();
					//System.out.println("KleinsterKreis - findeUmkreis() - KUK gefunden (Spezialfall 'nur noch drei Kreise im Set - Zweierpack'; winkelVergleichsWert uTop (a: " + uTop.a.xWert + "; " + uTop.a.yWert + "| b: -entfernt- | c: " + uTop.c.xWert + "; " + uTop.c.yWert + ") ist " + uTop.winkelVergleichsWert + "; r: " + radius + "; mp: " + mittelpunkt.xWert + "; " + mittelpunkt.yWert );
					return 2;
				}
				
			}
			
			// Standardfall mehr als 3 Kreise im Set
			// Es sind mehr als 3 Kreise im TreeSet, dann kann man da auch immer drei loeschen und zwei reinlegen
			if ( umkreisBaum.size() > 3 )
			{
				// Packe Kreis rein ( P-2, P-1, P+1);
				Umkreis neuEins = new Umkreis( punkteBehaelter.get( pMinusZweiStellplatz ), punkteBehaelter.get( pMinusEinsStellplatz ), punkteBehaelter.get( pPlusEinsStellplatz ) );
				umkreisBaum.add( neuEins );
				//System.out.println("----> Vorhaben: baue Kreis aus ( ( posB - 2 ) % n )[" + (pMinusZweiStellplatz) + "], ( ( posB - 1 ) % n )[" + (pMinusEinsStellplatz) + "] und ( ( posB + 1 ) % n )[" + (pPlusEinsStellplatz) + "]; neuer Kreis gebaut mit " + neuEins.toString() );
				
				// Packe Kreis rein( P-1, P+1, P+2);
				Umkreis neuZwei = new Umkreis( punkteBehaelter.get( pMinusEinsStellplatz), punkteBehaelter.get( pPlusEinsStellplatz ), punkteBehaelter.get( pPlusZweiStellplatz ) );
				umkreisBaum.add( neuZwei );
				
				//System.out.println("----> Vorhaben: baue Kreis aus ( ( posB - 1 ) % n )[" + ( pMinusEinsStellplatz ) + "], ( ( posB + 1 ) % n )[" + ( pPlusEinsStellplatz ) + "] und ( ( posB + 2 ) % n )[" + (pPlusZweiStellplatz) + "]; neuer Kreis gebaut mit " + neuZwei.toString() );
				//System.out.println("--> Packe die beiden Umkreise ins Set: U1 ( " + neuEins.toString() + ") und U2 ( " + neuZwei.toString() + ");");
				
				// loeschen von 3 Punktkreisen macht auch nur Sinn wenn man mehr als zwei Punkte im Behaelter hat
				// Debugging des TreeSets
				//int i2 = 0;
				//for ( Umkreis u : umkreisBaum)
				//{
				//	System.out.println("Umkreis Nummer " + i2 + " mit a: " + u.a.toString() + " | b: " + u.b.toString() + " | c: " + u.c.toString() +" | wvw: " + u.winkelVergleichsWert + " ; mp: " + u.berechneUndGibUmkreisMittelpunkt().toString() + "; radius: " + u.berechneUndGibRadius());
				//	i2++;
				//}
				
				// Debugging des Punktebehaelters
				//System.out.println("Punktebehaelter vor Loeschaktion ...");
				//int i4 = 0;
				//for ( Punkt p : punkteBehaelter)
				//{
				//	System.out.println("Punkt auf Stellplatz " + i4 + ": " + p.toString());
				//	i4++;
				//}
				//System.out.println();
				
				// Schwierigkeit
				// + beim Loeschen muss man die Kreise erwischen, diese liegen im Set aber nicht in einer bestimmten Reihenfolge
				// + der Punktebehaelter ist noch aktuell daher kann man ueber diesen gehen und mittels Index arbeiten
				// + Sets koennen die gleichen Kreise nur einmal anlegen, daher muesste ein remove auf den gleich angelegten Kreis klappen
				
				// Loesche die drei beteiligten Kreise aus dem Set
				// Kreis P-1, P, P+1
				Umkreis loeschKreisEins =  new Umkreis(punkteBehaelter.get( pMinusEinsStellplatz ), punkteBehaelter.get( (posB ) % n ), punkteBehaelter.get( pPlusEinsStellplatz ) );
				umkreisBaum.remove(loeschKreisEins);
				
				
				// Kreis P-2, P-1, P
				Umkreis loeschKreisZwei =  new Umkreis(punkteBehaelter.get( pMinusZweiStellplatz ), punkteBehaelter.get( pMinusEinsStellplatz ), punkteBehaelter.get( ( posB ) % n));
				umkreisBaum.remove(loeschKreisZwei);
				
				// Kreis P, P+1, P+2
				Umkreis loeschKreisDrei =  new Umkreis(punkteBehaelter.get( Math.abs( (posB) % n ) ), punkteBehaelter.get( pPlusEinsStellplatz ), punkteBehaelter.get( pPlusZweiStellplatz ) );
				umkreisBaum.remove(loeschKreisDrei);
				
				//System.out.println("--> Loesche Kreis Eins, Zwei, Drei und Referenzpunkt: RefPunkt ( " + (punkteBehaelter.get( (posB ) % n).toString() )  + " ), U1 ( " + loeschKreisEins.toString() + "), U2 ( " + loeschKreisZwei.toString() + ") und U3 ( " + loeschKreisDrei.toString() + " );");
				
				
				// Debugging des TreeSets
				//int i3 = 0;
				//for ( Umkreis u : umkreisBaum)
				//{
				//	System.out.println("Umkreis Nummer " + i3 + " mit a: " + u.a.toString() + " | b: " + u.b.toString() + " | c: " + u.c.toString() +" | wvw: " + u.winkelVergleichsWert + " ; mp: " + u.berechneUndGibUmkreisMittelpunkt().toString() + "; radius: " + u.berechneUndGibRadius());
				//	i3++;
				//}
				
				// Loesche den Punkt P aus dem Behaelter
				punkteBehaelter.remove(posB);
				
				// Debugging Punktebehaelter
				//System.out.println("Punktebehaelter nach Loeschung ...");
				//int i5 = 0;
				//for ( Punkt p : punkteBehaelter )
				//{
				//	System.out.println("Punkt Stellplatz " + i5 + ": " + p.toString());
				//	i5++;
				//}
				//System.out.println();
			}
			
			// versuche naechsten Kandidaten durch Selbstaufruf
			findeUmkreis();
		}
		
		// Verlauf-Meldung
		//System.out.println("ACHTUNG: KleinsterKreis - findeUmkreis() - Verlaufen!");
		return 1;
	}

 

[maki]

ich habe da nun was rekursiv geloest - klappt auch gut, wenn man 'normale' Mengen an Eingabepunkten in die Methode jagt - ab rund 300 gehts dann aber los - Stack Overflow.

Gibt/gab (?) mal einen Bug unter Windows: http://www.java-forum.org/allgemeine-java-themen/64258-rekursion-und-stackoverflow.html

Ansonsten gibt es natürlich die Möglichkeit, Rekursion in Iteration abzuändern, ist zwar selten schön, dafür aber schneller..

 

[Jay1980]

Ah das ging recht einfach und schnell, habs nun so gemacht - wenn jemandem was auffaellt, immer raus damit, ich brech eben nun gleich immer mit return aus der ganzen Methode aus und nicht nur aus der Schleife - ist das okay so, oder hat das Nachteile die ich so nicht sehe?

private int findeUmkreis() 
	{
		
		// Iterative Herangehensweise
		
		boolean loopFlag = true;
		while ( loopFlag == true )
		{
			// nimm den groessten Kreis
			Umkreis uTop = nimmGroesstenKreis();
			
			// Winkelvergleichswert
			if ( uTop.winkelVergleichsWert > 0 )
			{
				// KUK da
				radius = uTop.radius;
				mittelpunkt = uTop.berechneUndGibUmkreisMittelpunkt();
				
				// Ausbruch via Flagschalter, eigentlich tut es auch return
				//loopFlag = false;
				return 2;
			}
			else
			{
				// Noch kein Kreiskandidat
				
				// Eckdaten ermitteln
				int n = punkteBehaelter.size();
				int posB = punkteBehaelter.indexOf(uTop.b);
				
				// zwei neue Kreise aufnehmen
				// Zugriffsindex standardmaessig bestuecken
				int pMinusZweiStellplatz 	= ( posB - 2 ) % n;
				int pMinusEinsStellplatz 	= ( posB - 1 ) % n;
				
				int pPlusEinsStellplatz 	= ( posB + 1 ) % n;
				int pPlusZweiStellplatz 	= ( posB + 2 ) % n;
				
				// Ausnahmen abgreifen
				
				// Fall (test4.test) [geloest]: 
				// ArrayOutOfBounds, wenn posB kleiner als 2 ist bzw. wird, was soll also passieren,
				// wenn ich bei Index -1 auf das vorletzte zugreifen soll
				// n = 4, p ist auf 1, p-2 ist also -1, ist also ArrayOutOfBounds
				// Loesung waere Stelle 3, also n - Rest
				if (pMinusZweiStellplatz < 0 )
				{
					int pMinusZweiStellplatzAlt = pMinusZweiStellplatz; // Stellplatz ist etwa -1
					pMinusZweiStellplatz = n + pMinusZweiStellplatzAlt; // Stellplatz wird dann 4 + (-1), also 3
				}
				
				// Fall (random10.points), siehe Fall (test4.test)
				if (pMinusEinsStellplatz < 0 )
				{
					int pMinusEinsStellplatzAlt = pMinusEinsStellplatz; // Stellplatz ist etwa -1
					pMinusEinsStellplatz = n + pMinusEinsStellplatzAlt; // Stellplatz wird dann 4 + (-1), also 3
				}
				
				// Fall ( random5.test): 
				// gibt nur noch 3 Kreise im Set
				if ( umkreisBaum.size() < 4 )
				{
					// nimm uTop und schau dir den Winkel an
					if ( uTop.winkelVergleichsWert > 0) 
					{
						// Umkreis ist uTop im Dreierpaket
						radius = uTop.radius;
						mittelpunkt = uTop.berechneUndGibUmkreisMittelpunkt();
						
						return 2;
					}
					else
					{
						// Umkreis ist uTop ohne Referenzpunkt
						
						// Mittelpunkt der Strecke berechnen das ist der Umkreismittelpunkt
						mittelpunkt = uTop.berechneUndGibUmkreisMittelpunktEinerStrecke();
						
						// Radius einer Strecke
						radius = uTop.berechneUndGibRadiusEinerStrecke();
						return 2;
					}
					
				}
				
				// Standardfall mehr als 3 Kreise im Set
				// Es sind mehr als 3 Kreise im TreeSet, dann kann man da auch immer drei loeschen und zwei reinlegen
				if ( umkreisBaum.size() > 3 )
				{
					// Packe Kreis rein ( P-2, P-1, P+1);
					Umkreis neuEins = new Umkreis( punkteBehaelter.get( pMinusZweiStellplatz ), punkteBehaelter.get( pMinusEinsStellplatz ), punkteBehaelter.get( pPlusEinsStellplatz ) );
					umkreisBaum.add( neuEins );
					//System.out.println("----> Vorhaben: baue Kreis aus ( ( posB - 2 ) % n )[" + (pMinusZweiStellplatz) + "], ( ( posB - 1 ) % n )[" + (pMinusEinsStellplatz) + "] und ( ( posB + 1 ) % n )[" + (pPlusEinsStellplatz) + "]; neuer Kreis gebaut mit " + neuEins.toString() );
					
					// Packe Kreis rein( P-1, P+1, P+2);
					Umkreis neuZwei = new Umkreis( punkteBehaelter.get( pMinusEinsStellplatz), punkteBehaelter.get( pPlusEinsStellplatz ), punkteBehaelter.get( pPlusZweiStellplatz ) );
					umkreisBaum.add( neuZwei );
					
					
					// Loesche die drei beteiligten Kreise aus dem Set
					// Kreis P-1, P, P+1
					Umkreis loeschKreisEins =  new Umkreis(punkteBehaelter.get( pMinusEinsStellplatz ), punkteBehaelter.get( (posB ) % n ), punkteBehaelter.get( pPlusEinsStellplatz ) );
					umkreisBaum.remove(loeschKreisEins);
					
					
					// Kreis P-2, P-1, P
					Umkreis loeschKreisZwei =  new Umkreis(punkteBehaelter.get( pMinusZweiStellplatz ), punkteBehaelter.get( pMinusEinsStellplatz ), punkteBehaelter.get( ( posB ) % n));
					umkreisBaum.remove(loeschKreisZwei);
					
					// Kreis P, P+1, P+2
					Umkreis loeschKreisDrei =  new Umkreis(punkteBehaelter.get( Math.abs( (posB) % n ) ), punkteBehaelter.get( pPlusEinsStellplatz ), punkteBehaelter.get( pPlusZweiStellplatz ) );
					umkreisBaum.remove(loeschKreisDrei);
					
					// Loesche den Punkt P aus dem Behaelter
					punkteBehaelter.remove(posB);
					

				}
				// versuche naechsten Kandidaten durch Selbstaufruf, bzw. Schleifendurchgang
				// passiert automatisch
			}	
		}
		// Dummyreturn
		return 5;
}

 

[ARadauer]

Rekursion in Iteration abzuändern, ist zwar selten schön, dafür aber schneller..

ehrlich? findest du Rekursionen schön? Ich finde das Uni Schmarrn, das bei 50% der sinnvollen Anwendungen den Stack zum überlaufen bringt...

 

[0x7F800000]

ehrlich? findest du Rekursionen schön? Ich finde das Uni Schmarrn, das bei 50% der sinnvollen Anwendungen den Stack zum überlaufen bringt...

Ich kann irgendwie nicht so recht einschätzen, ob das ernst gemeint war^^ ???:L
Sicher bei mehr als 50% der sinnvollen Anwendungen verhält sich die Rekursionstiefe etwa wie O(n), und daher dürfte es meistens schwierig sein, den kompletten Speicher mit Rekursionsaufrufen zuzumüllen, ohne davor an irgendeiner anderen Stelle Stress mit Speicherplatz zu bekommen :bahnhof:
Fällt dir spontan irgendein beispiel ein? ???:L Rekursionen in Iterationen umzuschreiben ist leider eine ziemliche qual :autsch:

 

[ARadauer]

Fällt dir spontan irgendein beispiel ein?

alles was mit bildverarbeitung zu tun hat ;-)
Das waren wärend meiner Studienzeit die ersten praktischen Anwendungsbereiche für rekursive Funktionen, natürlich nicht zu gebrauchen ab 1600*1200 px Bildern ;-) darum hab ich so einen Hass auf Rekursionen

 

[0x7F800000]

alles was mit bildverarbeitung zu tun hat ;-)
Das waren wärend meiner Studienzeit die ersten praktischen Anwendungsbereiche für rekursive Funktionen, natürlich nicht zu gebrauchen ab 1600*1200 px Bildern ;-) darum hab ich so einen Hass auf Rekursionen

Tja, wärst du bloß nicht so ein Wunderkind, und hättest nicht mit dem 5. Semester angefangen, sondern dir erstmal die schönen kleinen Rekursionen aus den ersten 4 Semestern angeguggt... :bae: Was ist denn mit der ganzen Sortiererei, Bäumen, Composites, Graphen, Backtracking, Kollisionserkennung, Kombinatorik...?

Hab mich mit der Bildverarbeitung bisher nicht wirklich befasst, aber... versteh ich ehrlich gesagt immer noch nicht^^

log(10 000^2) / log(2) = 26.5754248

Diese Rekursionstiefe benötigt man, um jeden einzelnen Pixel von einem 10000x10000 Pixel großen bild rekursiv zu durchlaufen, wenn man jeden Bereich dauernd halbiert, bis man bis zu einem einzelnen Pixel kommt... 26 hört sich noch nicht so schlimm an :bahnhof:

Könntest du evtl irgendeinen konkreten Algo nennen, der trotz des korrekten Rekursionsabbruchs dazu tendiert, den gesamten Speicher zuzumüllen?

 

[Marco13]

void floodFill(int x, int y)
{
    if (!filled(x,y)) 
    {
        fill(x,y);
        floodFill(x+1,y);
        floodFill(x-1,y);
        floodFill(x,y+1);
        floodFill(x,y-1);
    }
}

!? :autsch:

 

[0x7F800000]

oh je... Okay... tatsächlich... :autsch: Aber da sieht man zum Glück sofort, dass die Rekursionstiefe nicht wie üblich logarithmisch zur anzahl der Pixel abfällt, sondern linear bleibt :noe: Da ist es ja klar, dass es einem um die Ohren fliegt... :bahnhof:

edit: hab's jetzt mal ausprobiert: es fliegt einem schon bei einem 150x150px Klecks um die Ohren omg^^ Okay ARadauer, ich hab jetzt mein horizont ein bisschen erweitert, und weiß dass es auch völlig unbrauchbare rekursive Algorithmen gibt^^ Heißt aber trotzdem nicht, dass Rekursion grundsätzlich unschön ist

@Jay1980: sorry dass wir hier deinen Thread mit philosophischen Quatsch zumüllen: das eigentliche Problem scheint aber gelöst zu sein?

 

[bygones]

ehrlich? findest du Rekursionen schön? Ich finde das Uni Schmarrn, das bei 50% der sinnvollen Anwendungen den Stack zum überlaufen bringt...

wenn man es nicht schafft seine Rekursion endrekursiv zu machen natuerlich...

 

[Jay1980]

@0x7F800000

Ja ich denke das habe ich so geschafft, das Programm liefert die gleichen Ergebnisse und ist auch etwas schneller. Ich war nur skeptisch, ob die Art und Weise wie ich die Rekursion in eine Iteration verwandelt habe, so 'schoen' ist. StackOverflow ist jetzt in jedem Fall behoben, daher das Problem geloest.

 

[musiKk]

Rekursionen für algorithmisch komplexe Dinge sind auch besser in Sprachen aufgehoben, die etwas davon verstehen. Besonders sind das funktionale Sprachen, welche meist auch Tail Recursion beherrschen. Der floodFill von oben dürfte ohne Änderung dadurch automatisch iterativ behandelt werden.
Viele Dinge lassen sich durch Rekursionen halt einfach elegant und kurz ausdrücken; wie auch der floodFill zeigt.

 

[Landei]

alles was mit bildverarbeitung zu tun hat ;-)
Das waren wärend meiner Studienzeit die ersten praktischen Anwendungsbereiche für rekursive Funktionen, natürlich nicht zu gebrauchen ab 1600*1200 px Bildern ;-) darum hab ich so einen Hass auf Rekursionen

Das Problem ist nicht Rekursion, sondern Java - genauer gesagt die Implementierung von Sun. Andere JVMs wie J9 von IBM haben Tail Call Optimierung (Endrekursion) eingebaut, bei der sich rekursiven Probleme so formulieren lassen, dass nie ein StackOverflow auftritt. Dazu muss nur der rekursive Aufruf die allerletzte Operation der Methode sein, dann kann man nähmlich den bestehenden StackFrame "recyclen". Die meisten funktionale Sprachen haben das schon ewig.

[edit]Oh sorry, ich hatte musiKK überlesen...[/edit]

 

[0x7F800000]

Hm? ???:L Tail recursion nützt aber beim floodfill gar nichts, denn da "verzweigt" sich was. Tail recursion ist nur dort vom Nutzen, wo schleifen durch rekursive funktionen/prädikate ausgedrückt werden, weil die Sprache keine Schleifen unterstützt. Bei floodfill kommt man halt nicht drumherum im Worstcase bei n Pixeln O(n) potentielle verzweigungspunkte abzuspeichern. Der Algorithmus ist an sich böse, da kann die JVM nicht dafür. Obwohl endrekursion natürlich schön wäre... das wurde doch alles schon Jahrzehnte vor Java erfunden und in 100 verschiedenen Funktionalen und logischen Sprachen implementiert, furchtbar dass es das in Java nicht gibt ;(

 

[Landei]

Kommt drauf an, wie man floodfill implementiert. Wenn man alle noch zu untersuchenden Pixel in einem Set oder so hält, reicht ein einziger Aufruf.

[edit]

Mal schnell in einer Sprache mit Tail-Rekursion implementiert:

object flood {
  val pic = Array(
    "#####################################",
    "#........#...................#......#",
    "#..................####.......#######",
    "#...#....#..........................#",
    "#...##...####################.......#",
    "#...#....#..........................#",
    "#####################################")

  def floodFill(pixels:Set[(Int,Int)]) {
   if (pixels.isEmpty) pic.foreach(println)
   else floodFill(pixels.foldLeft(Set[(Int,Int)]()){ (set, point) =>
        val (x,y) = point
        val line = pic(y).toArray
        line(x) = 'X'
        pic(y) = line.mkString("")
        set ++ List((-1,0),(1,0),(0,-1),(0,1)).map(p => (p._1+x,p._2+y)).
        filter(p => pic(p._2).charAt(p._1) == '.')
    })}

  def main(args:Array[String]) {
    floodFill(Set((2,2)))
  }

}

Ausgabe:
#####################################
#XXXXXXXX#XXXXXXXXXXXXXXXXXXX#......#
#XXXXXXXXXXXXXXXXXX####XXXXXXX#######
#XXX#XXXX#XXXXXXXXXXXXXXXXXXXXXXXXXX#
#XXX##XXX####################XXXXXXX#
#XXX#XXXX#XXXXXXXXXXXXXXXXXXXXXXXXXX#
#####################################

 

[musiKk]

Tail recursion nützt aber beim floodfill gar nichts, denn da "verzweigt" sich was.

Naja, stimmt schon. In der Form ist der Algorithmus vielleicht nicht optimierbar. Sicher wäre ich mir aber erst nach Ausprobieren. Compiler werden auch oft genug unterschätzt.

 

[Landei]

Siehe meinen letzten Beitrag: floodFill mit Endrekursion

 

[0x7F800000]

@Landei: Ja, gut, wenn man da aber irgendeine Warteschlange dranbaut, dann hat man sich ja schon quasi die iterative version des Algorithmus überlegt, und braucht die Rekursion gar nicht mehr, diese endrekursive methode macht einfach dasselbe wie eine Schleife. Das ist eine andere herangehensweise.

@musiKk: nein. Die kurze & anschauliche aber speicherfressende Version, so wie Marco13 sie hingeschrieben hat, lässt sich mit keinem Compiler retten, es sei denn er ist schlauer als der programmierer, und lässt sich einfach so neue & bessere Algorithmen einfallen. Wenn es soweit ist, sind wir als Programmierer arbeitslos und als Spezies überflüssig. ;(

 

[Godric]

also ich leibe rekursion! speziell im umgang mit listen(eigenen), aber ok ich schweife ab :/

 

[Landei]

@Landei: Ja, gut, wenn man da aber irgendeine Warteschlange dranbaut, dann hat man sich ja schon quasi die iterative version des Algorithmus überlegt, und braucht die Rekursion gar nicht mehr, diese endrekursive methode macht einfach dasselbe wie eine Schleife. Das ist eine andere herangehensweise.

Na ja, nicht ganz. Ich verwende ein Set, eine Liste oder Queue würde hier nicht ohne weiteres funktionieren. Es wäre eine interessante Frage, ob man für Mehrfach-Rekursion (wie den originalen Flood Fill) "automatisch" eine Umformung in Einfachrekursion anbieten kann, zumindest in Fällen, wo die Abarbeitungsreihenfolge egal ist (wie eben bei Flood Fill).

 

[musiKk]

Es wäre eine interessante Frage, ob man für Mehrfach-Rekursion (wie den originalen Flood Fill) "automatisch" eine Umformung in Einfachrekursion anbieten kann, zumindest in Fällen, wo die Abarbeitungsreihenfolge egal ist (wie eben bei Flood Fill).

Das habe ich mich auch gefragt, aber laut unserer Hex-Zahl, ist das ja mit "keinem Compiler zu retten". Ergo ist das Problem ja gelöst...

Eine kurze Googelei zu "multiple tails" brachte noch keine sinnvollen Ergebnisse. Wäre vielleicht eine Frage für LtU.

 

[0x7F800000]

Na ja, nicht ganz. Ich verwende ein Set, eine Liste oder Queue würde hier nicht ohne weiteres funktionieren.

Äähm, ja, irgendsowas Set-mäßiges, was nicht notwendigerweise die Reihenfolge behält... Dass jeder Pixel 1 mal eingefügt wird ist da natürlich wesentlich

Das habe ich mich auch gefragt, aber laut unserer Hex-Zahl, ist das ja mit "keinem Compiler zu retten".

Es sei denn der Compiler ist schlauer als der Programmierer Das ist ja in meinem Fall nicht ausgeschlossen :rtfm: