• Announcements

    • Lars

      Allgemeine Forenregeln   03/13/2017

      Forenregeln Nimm dir bitte einen Moment um die nachfolgenden Regeln durchzulesen. Wenn du diese Regeln akzeptierst und die Registration fortsetzen willst, klick einfach auf den "Mit der Registrierung fortfahren"-Button. Um diese Registration abzubrechen, klick bitte einfach auf den "Zurück" Button deines Browsers. Wir garantieren nicht für die Richtigkeit, Vollständigkeit und Brauchbarkeit der Nachrichten und sind auch nicht dafür verantwortlich. Die Beiträge drücken die Meinung des Autors des Beitrags aus, nicht zwangsläufig das, wofür die Forensoftware steht. Jeder Nutzer, der denkt, dass ein veröffentlichter Beitrag unzulässig bzw. störend ist, ist aufgefordert uns unverzüglich per E-Mail zu kontaktieren. Wir haben das Recht störende Beiträge zu löschen und bemühen uns, das in einem realistischem Zeitraum zu erledigen (sofern wir beschlossen haben, dass die Löschung notwendig ist). Du akzeptierst, durchgehend während der Nutzung dieses Services, dass du dieses Forum nicht dazu missbrauchen wirst, Inhalte zu veröffentlichen, welche bewusst falsch und/oder verleumderisch, ungenau, beleidigend, vulgär, hasserfüllt, belästigend, obszön, sexuell belästigend, bedrohlich, die Privatsphäre einer Person verletzend oder in irgend einer Art und Weise das Gesetz verletzen. Des Weiteren akzeptierst du, dass du keine urheberrechtlich geschützte Inhalte ohne Erlaubnis des Besitzers in diesem Forum veröffentlichst. Mit dem Klick auf den "Mit der Registrierung fortfahren"-Button, akzeptierst du zudem unsere Datenschutzerklärung und stimmst der Speicherung deiner IP-Adresse und personenbezogenen Daten zu, die dafür benötigt werden, um dich im Falle einer rechtswidrigen Tat zurückverfolgen zu können bzw. permanent oder temporär aus dem Forum ausschließen zu können. Es besteht keine Pflicht zur Abgabe der Einwilligung, dies erfolgt alles auf freiwilliger Basis.   Zusatzinformationen Der Forenbetreiber hat das Recht, Nutzer ohne Angabe von Gründen permanent aus dem Forum auszuschließen. Des Weiteren hat er das Recht, Beiträge, Dateianhänge, Umfrage, Blogeinträge, Galleriebilder oder Signaturen ohne Angabe von Gründen zu entfernen. Mit der Registrierung verzichtest du auf alle Rechte an den von dir erstellten Inhalten, bzw. treten diese an das Unity-Insider.de und Unity-Community.de ab. Dies bedeutet im Klartext, dass das Unity-Insider.de und Unity-Community.de frei über deine Texte verfügen kann, sofern diese nicht wiederum die Rechte anderer verletzen. Es besteht weiterhin kein Anspruch von registrierten Nutzern bzw. ehemaligen registrierten Nutzern darauf, dass erstellte Inhalte und/oder die Mitgliedschaft (User) wieder gelöscht werden (Erhaltung der Konsistenz dieses Forums).   Einwilligungserklärung Wenn du mit der Speicherung deiner personenbezogenen Daten sowie den vorstehenden Regeln und Bestimmungen einverstanden bist, kannst du mit einem Klick auf den Mit der Registrierung fortfahren-Button unten fortfahren. Ansonsten drücke bitte Zurück. Stand: 07.03.2011
Sign in to follow this  
Followers 0
N_Gnom

Ich frag mal am Rande: Rekursive Programmierung

7 posts in this topic

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.

Share this post


Link to post
Share on other sites

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.
 

 

 

Share this post


Link to post
Share on other sites

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 ;)

Share this post


Link to post
Share on other sites

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?

Share this post


Link to post
Share on other sites

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"....

 

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

@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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0