Rekursion einfach erklärt - Funktionen in Java 5
Informatik - simpleclub
https://www.youtube.com/watch?v=weTpjhDnLnc

Transkript (automatisch erstellt)

0:10 Aha da ist sie also: Die berühmte, weltbekannte, glorreiche Rekursion. Oh man lass mich raten: “Wenn ihr die verstanden habt, dann habt
0:19 ihr fast die ganze Informatik verstanden” So oder so änhlich erzählt das der Prof doch immer :D
0:23 Schauen wir uns das mal in Ruhe an! Und ab geht’s!
0:26 INTRO Erklärung Was ist Rekursion? Also gut Freunde!
0:32 Was bedeutet jetzt Rekursion? Bei der Rekursion ruft sich eine Methode quasie wieder selbst auf.
0:37 Das heißt wir haben eine Methode in unsrem Progamm, die sich immer wieder selbst aufruft, bis eine bestimmte Abbruchbedingung erfüllt ist.
0:46 Es gibt die indirekte und direkte Rekursion. Indirekt bedeutet zwei Methoden rufen sich wechselseitig auf.
0:53 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
1:02 Lösung wieder vereint. Auch bekannt als Prinzip “Teile und Herrsche” :) #Sidefact.
1:08 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
1:14 Um das zu tun führt sie die Methode Baum fällen aus. Die Methode wird jedesmal neu aufgerufen.
1:20 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.
1:26 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.
1:34 Am Ende ist klar sie bekommt einen Weihnachtsbaum :D Am besten wir schauen mal die baumfällende Oma im Code an:
1:40 Beispiel Rekursion baumfällende Oma Also wie gesagt: Unsre Oma geht in den Wald.
1:44 Dort will sie Bäume für Weihnachten fällen. ~
1:47 Das heißt wir machen ein Methode baumfällen. Dabei geben wir kein bestimmte Typ zurück, deswegen schreiben wir void.
1:52 Als Parameter übergeben wir eine beliebige Zahl. Die soll einfach die Dicke des Stamms wiederspiegeln.
1:58 Jetzt kommen die Anweisungen. Als erstes hackt die Oma den Baum.
2:02 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
2:10 Baum. Ansonsten wiederhole die Funktion von Anfang.
2:13 Die Zeile 12 ist dabei die eigentliche Rekursion. Hier rufen wir die Methode baumfällen erneut auf und übergeben ihr den Parameter abzüglich
2:21 1. So eine Art Abbruchbedingung ist ganz wichtig, damit die Methode irgendwann auch zum Ende
2:26 kommt. Sonst würde die Oma ewig das Holz hacken.
2:29 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.
2:38 Alright! Dann noch schnell die Main Methode dazu.
2:41 Wir rufen unsre Methode dann direkt auf. Und übergeben die Zahl 5.
2:45 Das heißt im Kontext der Stamm hat eine größe von 5. Wie dick das jetzt ist könnt ihr euch selbst ausdenken.
2:51 Starten wir jetzt das Programm erhalten wir…. Die Oma hackt also 5 mal den Baum und hat dann schon den ersten Weihnachtsbaum.
2:59 Erklärung Wdh Iteration Man erkennt leicht, dass man dieses Beispiel auch mit einer Schleife hätte lösen können.
3:04 Das ist dann wieder das Konzept der Iteration. Wat war das nochmal?
3:07 Bei der Iteration werden bestimmte Abschnitte eines Programms einfach nochmal wiederholt. Dabei wird aber nicht die komplette Methode erneut aufgerufen.
3:15 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
3:24 aus einer Iteration eine Rekursion und umgekehrt zu machen. Das letzte mal, haben wir uns die Fakultätsfunktion angeschaut.
3:32 Iterativ sieht dat ganze dann so aus: Eben mir einer For Schleife, damit ein bestimmter Abschnitt der Methode wiederholt wird.
3:38 Beispiel Rekursion Fakultät Jetzt wollen wir mal die Fakultät rekursiv programmieren.
3:42 Dazu erstmal wieder eine neue Klasse. Danach gleich die Methode: Wir nennen sie einfach wieder “rechneFakultät”.
3:49 Der Methode übergeben wir wieder eine Zahl, aus der dann die Fakultät berechnet wird. Jetzt schreiben wir gleich die Abbruchbedingung.
3:56 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.
4:06 Dabei passiert der rekursive Aufruf. Wir schreiben a * rechneFakultaet(a-1).
4:11 Das heißt unsre Methode beginnt wieder von vorne, aber verringert vorher die Zahl die wir bestimmen um eins.
4:19 Schreiben wir jetzt unsre Main Methode noch dazu und testen das ganz mit der 3. Und schwups die wups erhalten wir als Ergebnis 6.
4:27 Wie läuft das jetzt also ab? Im Prinzip haben folgende Bausteine im Code Parameterübergabe
4:34 If Anweisung oder die Else Anweisung
4:37 Wir starten die Methode mit der 3 als Eingabe. Sprich wir übergeben sie.
4:42 Jetzt wird geprüft, ob 3 kleiner gleich 1 ist. Ne absolut nicht!
4:46 Also springen wir in den Else Fall. Das heißt wir geben jetzt zurück: 3 mal rechneFakultaet(3-1)
4:54 Jetzt beginnt der ganze Spaß wieder von vorne: Diesmal ist der Wert aber nur noch 2 statt 3.
4:59 2 ist größer als 1, also wieder ab in den Else Fall.
5:03 Dort wieder 2* rechneFakultaet (2-1) Insgesamt steht jetzt also da: 3 * 2 * rechneFakultaet(1)
5:11 Man sieht ganz gut, dass das Programm die Zahl in immer kleinere Teile zerlegt. Dadurch wird die Rechnung immer länger.
5:19 Erneut rufen wir als die Methode auf, aber diesmal mit der 1. 1 ist kleiner gleich 1.
5:25 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.
5:33 Was laut Adam Riese gleich 6 ergibt. Nice!
5:36 Wichtig ist also: Bei der Rekursion wird die Methode immer und immer erneut aufgerufen, bis sie irgendwann die Abbruchbedingung erreicht.
5:44 Bei der Fakultät wird die erste Zahl in immer kleiner Zahlen zerlegt und am Ende wird alles zusammengerechnet.
5:51 Logischerweise gibt es noch zahlreiche verschiedene Varianten, die Fakultät rekursiv zu programmieren. Aber das überlassen wir eurer Kreativität.
5:58 Als Tipp: Probiert mal den Rekursiven Aufruf in den If Zweig zu packen und die Abbruchbedingung in den Else Zweig.
6:05 Erklärung Vergleich Rekursion vs Iteration Iteration und Rekursion sind sich sehr ähnlich.
6:10 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.
6:17 #warjaklar :D Am besten ihr versucht selbst noch ein paar Rekursive Programme zu schreiben, damit das
6:21 Konzept klar wird. Aber vorher verschaffen wir uns nochmal ein Überblick.
6:25 Zusammenfassung Unter Rekursion versteht man das Selbstaufrufen einer Methode.
6:29 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.
6:39 Bei indirekter Rekursion können sich zwei Methoden wechselseitig aufrufen. Vergleichbar mit der Rekursion ist die Iteration.
6:46 Dort werden bestimmte Abschnitte wiederholt. Das wird meist mit einer Schleife realisiert.
6:52 Man kann sowohl Iterative Methoden in Rekursive umschreiben, als auch umgekehrt. Ja jut geil!
6:57 Dat wars auch wieder Freunde. Wenn ihr noch mehr sehen wollt, dann geht auf unsre Lernplattform.
7:02 Bis dahin haut rein und bis gleich.