Jump to content
Unity Insider Forum

Ich frag mal am Rande: Rekursive Programmierung


N_Gnom

Recommended Posts

Da hier ja doch so einige Könner dabei sein dürften....

Und zwar, wie rekursive programmierung theoretisch funktioniert hab ich verstanden, aber mir fehlt es an der Umsetzung.

Also ich hab mir Beispiele zu Potenz, Türme von Hanoi und Fibonacci-Folge angeschaut.

So richtig verstehen tu ichs noch nicht.

Vielleicht liegts auch daran dass ich mir zuviel "querangeschaut" habe.

Ich bin nun völlig verwirrt....mich würde die korrekte Funktionsweise anhand z.b. eben einer Potenzierungfunktion und vielleicht hmmm keine Ahnung eine Suchfunktion o.ä. interessieren.

Vorallem was zu welchem Zeitpunkt des Durchlaufs bis zum bedingten Abbruch wo (zwischen)gespeichert ist.

Vielleicht leuchtet es mir ja dann ein.

Gerade zum Beispiel Potenzfunktion hab ich inzwischen soviele Codes gesehen wovon wahrscheinlich ein großer Teil unsinnig oder gar falsch war.

Könnte mir das jemand mal total einfach erläutern?

Ich denk mal so oft werd ich nicht rekursiv anwenden müssen, aber ich hab mir eben in den Kopf gesetzt das verstehen zu wollen.

Iterativ ists kein Problem.

Es kann auch gerne pseudocode sein.

 

Ich wäre echt dankbar wenn sich da mal jemand die mühe machen könnte.

Link zu diesem Kommentar
Auf anderen Seiten teilen

Ich will es dir mal am Beispiel der Fakultät versuchen zu erklären.
Dort multipliziert man ja alle natürlichen Zahlen von 1 an bis zur Angegebenen.

Also bei der Fakultät von 5 würdest du 1*2*3*4*5 rechnen und kämst auf auf das Produkt 120.

Hier hast du jetzt 2 Werte, die du für deine Rekursion brauchst. Einmal die 5 welche du deiner rekursiven Berechnungsfunktion übergibst und einmal die 1, welche die kleinste natürliche Zahl für solch eine Berechnung ist.

Du hast jetzt in irgendeinem Script solch eine Funktion die du Aufrufst und den Zielwert, z.B. unsere 5, übergibst. Diese Funktion ist jetzt rekursiv und wirderholt sich ständig selbst, bis etwas eingetreten ist, was sie zum Beenden und Übergeben des Ergebnisses bringt.

Das hier wäre der Aufrunf:

long ergebnis =Fakultaet(5); // hier wird die Funktion aufgerufen und die gewünschte Zahl übergeben. 
print(ergebnis); // das, was ich zurück bekomme, wird jetzt ausggeben.

Die Funktion sähe dann so aus:

public long Fakultaet(int wert){
	
	if (wert==1){  // wenn mein Wert 1 ist muss ich aufhören, denn sonst würde der nächste durchlauf mit der 0 sein.
		return 1;
	}	
	else{
		long ergebnis = wert*Fakultaet(wert-1); // hier rufe ich mich für die Berechnung selber nochmal auf, aber diesmal mit dem wert - 1
		return ergebnis;
	}
}

Entscheidend ist bei der Rekursion, dass von hinten nach vorne gerechnet wird, denn:

Ich rufe die Funktion mit dem Wert 5 auf.
In der Funktion wird überprüft ob der Wert 1 ist, und da er es ja jetzt noch nicht ist, ruft sich über  else  die Funktion selber nocheinmal auf. Diesmal aber mit reduziertem Wert, also der 4. Das Ergebnis wird noch nicht übergeben, denn der Pointer ist jetzt noch nicht da, sondern noch im 2ten Aufruf.
Im 2ten Aufruf wird wieder überprüft ob es die 1 ist. Ist es ja nicht, denn es ist die 4 also kommt wieder es zu einen weiteren Selbstaufruf, aber diesmal mit der 3.
so geht das weiter, bis der wert nur noch 1 groß ist.
Jetzt beginnt die Aufdröselung von hinten nach vorne!

Der letzte Aufruf hat erkannt dass wert 1 groß ist und somit wird über return die 1 zurückgegeben.
Die 1 bekommt jetzt der Aufruf davor zurück , der selber in der variable wert noch die 2 stehen hatte und rechnet jetzt 1*2. Das Ergebnis (2) wird per return dem Aufruf davor geben.
Der hat als eigenen Wert ja die 3 und multipliziert seinen Wert mit der Rückgabe, welches ja die 2 ist. Auch dieses Ergebnis (6) wird dem Aufruf davor übergeben.
Auch hier wird der eigene Wert 4 mit dem Rückgabewert 6 multipliziert und das Ergebnis (24) mit return dem Aufruf davor übergeben.
Jetzt sind wir an der oberen Ebene angelangt und die Berechnung aus eigenen Wert 5, das ist ja die Zahl gewesen die von dir an die Funktion übergeben wurde, und dem Ergebnis aus dem Selbstaufruf (24) wird jetzt multipliziert und über return deinem Aufruf zurück gegeben, und wird dann per print Befehl in der Konsole ausgegeben.

Du siehst jetzt hoffentlich, dass sich eine rekursive Funktion immer so lange selber aufruft, bis ein gewisses Ereignis eintritt, welche erst dann von unten nach oben die Berechnungen ausführt und dem Aufrufenden übergibt. Hast du keine Endbedingung für den Selbstaufruf, wird das so lange weiter gehen, bis der Rechner irgendwann aus Speichermangel oder aber das Programm z.B. StackOverflow bringt.

Eine Endbedingung kann alles Mögliche sein, aber kein Zwischenergebnis, da ja noch nichts berechnet wurde.

Ein anderes Beispiel wäre das Zählen aller Dateien in allen Verzeichnissen auf der Festplatte oder in einem Ordner.

PseudoCode:

verzeichnis start =new Verzeichnis("."); // wo soll gezählt werden
int ergebnis = ZaehleDateine(start) 
print (ergebnis);


public int ZaehleDateien(verzeichnis start){
	int zahl=1; 
	
	if(start == einVerzeichnis){ // die bedingung für den selbstaufruf
		alle Dateien in ein Array schieben;

		for(alle Dateien im Array){
			int unterDateien = ZaehleDateien(datei); // selbstaufruf für unterverzeichnis
			zahl += unterDateien;	
		}		
	}
	return zahl;
}

Auch hier bekommst du kein Zwischenergebnis, denn erst wenn alle Selbstaufrufe vom letzten her kommend abgearbeitet sind, wird deinem Aufruf ein Ergebnis zurück gegeben.
 

 

 

Link zu diesem Kommentar
Auf anderen Seiten teilen

Ich danke dir...sehr gut erklärt.

Ich hab den Fehler gemacht dass ich zwischendurch Beispiele wie z.b. die türme von Hanoi habe versucht zu verstehen.

Die theoretische Funktionsweise war mir ja bekannt, aber deine genaue Erklärung hat mir sozusagen jetzt nochmal mit einer Fackel den Weg gewiesen.

Danke dir, denn es ist ja eigentlich nicht schwer.

Die Türme von Hanoi interessieren mich immer noch, aber vielleicht komm ich da ja selber dahinter.

Aber nicht mehr heute ;)

Link zu diesem Kommentar
Auf anderen Seiten teilen

Freut mich wenn ich's erklären konnte.
Aber das mit den Türmen von Hanoi verstehe ich nicht so recht. Da ist doch nur die Abfrage, ob der zu bewegende Stein denn kleiner ist als der, auf dem ich ablegen will. Und ein leeres Feld ist immer größer als alle anderen Steine.
Was kann man denn da rekursiv lösen?

Link zu diesem Kommentar
Auf anderen Seiten teilen

Ehrlich gesagt, keine Ahnung.

Ich hatte nur eben gelesen dass es da wohl auch irgendwo ein Beispiel gäbe.

Es gibt ja auch verschiedene Lösungswege bzw. Spielregeln dafür.

 

P.S. Warum sind die Abstände in meinen posts eigentlich zwischen den Zeilen so groß?

Ah nur wenn man manuell "entert"....

 

Link zu diesem Kommentar
Auf anderen Seiten teilen

Der Lösungsalgorithmus für die Türme von Hanoi ist ein beliebtes Beispiel für rekursive Funktionen. Der Grund ist, dass zum Verschieben eines 5er-Turmes der obere 4er-Turm verschoben muss, dafür der obere 3er-Turm usw.

Zur Implementation des Spiels, sodass der Spieler es löst, ist Rekursion allerdings nicht sonderlich brauchbar.

Link zu diesem Kommentar
Auf anderen Seiten teilen

@sascha: Ah ok.

@N_Gnom: Unsere neue Forumsoftware macht es jetzt eigentlich nur so wie es Wordpress und andere Blogsysteme machen.
Mit Enter bzw. Return alleine hast du einen neuen Absatz. Mit Shift + Enter bzw. Return Hast du eine neue Zeile, ohne den Abstand zwischen den 2 Zeilen.

Link zu diesem Kommentar
Auf anderen Seiten teilen

Archiviert

Dieses Thema ist jetzt archiviert und für weitere Antworten gesperrt.

×
×
  • Neu erstellen...