Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Rekursion einfach erklärt - Funktionen in Java 5
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 69 Zeilen
- Aha da ist sie also: Die berühmte, weltbekannte, glorreiche Rekursion. Oh man lass mich raten: “Wenn ihr die verstanden habt, dann habt
- ihr fast die ganze Informatik verstanden” So oder so änhlich erzählt das der Prof doch immer :D
- Schauen wir uns das mal in Ruhe an! Und ab geht’s!
- INTRO Erklärung Was ist Rekursion? Also gut Freunde!
- Was bedeutet jetzt Rekursion? Bei der Rekursion ruft sich eine Methode quasie wieder selbst auf.
- Das heißt wir haben eine Methode in unsrem Progamm, die sich immer wieder selbst aufruft, bis eine bestimmte Abbruchbedingung erfüllt ist.
- Es gibt die indirekte und direkte Rekursion. Indirekt bedeutet zwei Methoden rufen sich wechselseitig auf.
- Eine direkte Rekursion ruft die eigene Methode selbst wieder auf. Dabei wird eine Aufgabe oder ein Problem in immer kleinere Teile zerlegt und am Ende zur
- Lösung wieder vereint. Auch bekannt als Prinzip “Teile und Herrsche” :) #Sidefact.
- Aha und wie kann ich mir das jetzt Vorstellen? Stellt euch vor eure Oma geht in den Wald und will Bäume für Weihnachten fällen :D
- Um das zu tun führt sie die Methode Baum fällen aus. Die Methode wird jedesmal neu aufgerufen.
- Das heißt sie führt mit ihrer Axt immer wieder dieselbe Bewegung aus. Sozusagen ruft sie immer wieder die Methode Baum fällen auf.
- Und jedesmal wird der Stamm des Baums dünner, bis sie ihn endlich gefällt hat. :D Durch den rekursiven Aufruf, macht sie also immer das gleiche.
- Am Ende ist klar sie bekommt einen Weihnachtsbaum :D Am besten wir schauen mal die baumfällende Oma im Code an:
- Beispiel Rekursion baumfällende Oma Also wie gesagt: Unsre Oma geht in den Wald.
- Dort will sie Bäume für Weihnachten fällen. ~
- Das heißt wir machen ein Methode baumfällen. Dabei geben wir kein bestimmte Typ zurück, deswegen schreiben wir void.
- Als Parameter übergeben wir eine beliebige Zahl. Die soll einfach die Dicke des Stamms wiederspiegeln.
- Jetzt kommen die Anweisungen. Als erstes hackt die Oma den Baum.
- Also drucken wir “hacken” auf der Konsole aus. Ist der Baum bei 1, das heißt bei uns die Dicke des Baums ist bei 1, dann fällt der
- Baum. Ansonsten wiederhole die Funktion von Anfang.
- Die Zeile 12 ist dabei die eigentliche Rekursion. Hier rufen wir die Methode baumfällen erneut auf und übergeben ihr den Parameter abzüglich
- 1. So eine Art Abbruchbedingung ist ganz wichtig, damit die Methode irgendwann auch zum Ende
- kommt. Sonst würde die Oma ewig das Holz hacken.
- Am besten ihr merkt euch: Bei der Rekursion ruft sich die Methode irgendwo selbst auf und sorgt dafür, dass es nach endlich vielen Aufrufen beendet wird.
- Alright! Dann noch schnell die Main Methode dazu.
- Wir rufen unsre Methode dann direkt auf. Und übergeben die Zahl 5.
- Das heißt im Kontext der Stamm hat eine größe von 5. Wie dick das jetzt ist könnt ihr euch selbst ausdenken.
- Starten wir jetzt das Programm erhalten wir…. Die Oma hackt also 5 mal den Baum und hat dann schon den ersten Weihnachtsbaum.
- Erklärung Wdh Iteration Man erkennt leicht, dass man dieses Beispiel auch mit einer Schleife hätte lösen können.
- Das ist dann wieder das Konzept der Iteration. Wat war das nochmal?
- Bei der Iteration werden bestimmte Abschnitte eines Programms einfach nochmal wiederholt. Dabei wird aber nicht die komplette Methode erneut aufgerufen.
- Viele Probleme oder Aufgaben werden entweder mit der Iteration oder mit der Rekursion gelöst. Beide Prinzipien erzielen meistens die gleichen Ergebnisse, deswegen ist es auch möglich
- aus einer Iteration eine Rekursion und umgekehrt zu machen. Das letzte mal, haben wir uns die Fakultätsfunktion angeschaut.
- Iterativ sieht dat ganze dann so aus: Eben mir einer For Schleife, damit ein bestimmter Abschnitt der Methode wiederholt wird.
- Beispiel Rekursion Fakultät Jetzt wollen wir mal die Fakultät rekursiv programmieren.
- Dazu erstmal wieder eine neue Klasse. Danach gleich die Methode: Wir nennen sie einfach wieder “rechneFakultät”.
- Der Methode übergeben wir wieder eine Zahl, aus der dann die Fakultät berechnet wird. Jetzt schreiben wir gleich die Abbruchbedingung.
- Ist die eingegebene Zahl kleiner oder gleich 1, dann gib uns eine 1 zurück. Ist die Zahl größer rechnet das Programm die eingegebene Zahl mal die erneute Funktion.
- Dabei passiert der rekursive Aufruf. Wir schreiben a * rechneFakultaet(a-1).
- Das heißt unsre Methode beginnt wieder von vorne, aber verringert vorher die Zahl die wir bestimmen um eins.
- Schreiben wir jetzt unsre Main Methode noch dazu und testen das ganz mit der 3. Und schwups die wups erhalten wir als Ergebnis 6.
- Wie läuft das jetzt also ab? Im Prinzip haben folgende Bausteine im Code Parameterübergabe
- If Anweisung oder die Else Anweisung
- Wir starten die Methode mit der 3 als Eingabe. Sprich wir übergeben sie.
- Jetzt wird geprüft, ob 3 kleiner gleich 1 ist. Ne absolut nicht!
- Also springen wir in den Else Fall. Das heißt wir geben jetzt zurück: 3 mal rechneFakultaet(3-1)
- Jetzt beginnt der ganze Spaß wieder von vorne: Diesmal ist der Wert aber nur noch 2 statt 3.
- 2 ist größer als 1, also wieder ab in den Else Fall.
- Dort wieder 2* rechneFakultaet (2-1) Insgesamt steht jetzt also da: 3 * 2 * rechneFakultaet(1)
- Man sieht ganz gut, dass das Programm die Zahl in immer kleinere Teile zerlegt. Dadurch wird die Rechnung immer länger.
- Erneut rufen wir als die Methode auf, aber diesmal mit der 1. 1 ist kleiner gleich 1.
- Das heißt wir springen gleich in den If Zweig und geben einfach die 1 zurück. Insgesamt haben wir also dann dastehen: 3 * 2 * 1.
- Was laut Adam Riese gleich 6 ergibt. Nice!
- Wichtig ist also: Bei der Rekursion wird die Methode immer und immer erneut aufgerufen, bis sie irgendwann die Abbruchbedingung erreicht.
- Bei der Fakultät wird die erste Zahl in immer kleiner Zahlen zerlegt und am Ende wird alles zusammengerechnet.
- Logischerweise gibt es noch zahlreiche verschiedene Varianten, die Fakultät rekursiv zu programmieren. Aber das überlassen wir eurer Kreativität.
- Als Tipp: Probiert mal den Rekursiven Aufruf in den If Zweig zu packen und die Abbruchbedingung in den Else Zweig.
- Erklärung Vergleich Rekursion vs Iteration Iteration und Rekursion sind sich sehr ähnlich.
- Rekursion ist manchmal die kürzere Variante, wenn auch ein a bissal komplizierter. Wird jedoch sehr häufig verwendet und ist auch bei euren Profs sehr beliebt.
- #warjaklar :D Am besten ihr versucht selbst noch ein paar Rekursive Programme zu schreiben, damit das
- Konzept klar wird. Aber vorher verschaffen wir uns nochmal ein Überblick.
- Zusammenfassung Unter Rekursion versteht man das Selbstaufrufen einer Methode.
- Damit die Selbst Aufrufe nicht unendlich werden, benötigt man immer eine Abbruchbedingung. Bei direkte Rekursion ruft sich die Methode irgendwo von selbst wiede auf.
- Bei indirekter Rekursion können sich zwei Methoden wechselseitig aufrufen. Vergleichbar mit der Rekursion ist die Iteration.
- Dort werden bestimmte Abschnitte wiederholt. Das wird meist mit einer Schleife realisiert.
- Man kann sowohl Iterative Methoden in Rekursive umschreiben, als auch umgekehrt. Ja jut geil!
- Dat wars auch wieder Freunde. Wenn ihr noch mehr sehen wollt, dann geht auf unsre Lernplattform.
- Bis dahin haut rein und bis gleich.
Zum Nachlesen
Rekursive ProgrammierungBei der rekursiven Programmierung ruft sich eine Prozedur, Funktion oder Methode in einem Computerprogramm selbst wieder auf (d. h. enthält eine Rekursion).
RekursionAls Rekursion (lateinisch recurrere ‚zurücklaufen') wird ein prinzipiell unendlicher Vorgang bezeichnet, der sich selbst als Teil enthält oder mithilfe von sich …
EntrekursivierungEntrekursivierung bezeichnet in der Informatik das Umwandeln einer rekursiven Funktion in eine iterative Funktion. Rekursionen sind eine Technik, …
AbbruchbedingungEine Abbruchbedingung ist in der Informatik eine Bedingung, die erfüllt sein muss, damit ein Vorgang beendet wird. Jede Schleife oder rekursive Funktion …