Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Rekursion
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 71 Zeilen
- Was ist Rekursion? Rekursion? Siehe Rekursion! In diesem Video sprechen wir über Rekursion. Was ist überhaupt Rekursion? Ganz einfach, von Rekursion spricht man, wenn ein Algorithmus
- sich selbst aufruft. Also ein Algorithmus A ruft sich direkt selbst auf oder es kann auch sein, dass ein Algorithmus A einen Algorithmus B aufruft und der ruft einen Algorithmus
- C auf und der ruft dann wieder A auf und so weiter. Das sieht jetzt aus wie eine Schleife. Das Gegenteil von rekursiv nennt man iterativ. Ein iterativer Algorithmus
- ruft sich also nicht selbst auf, weder unmittelbar noch mittelbar. Hier ein Beispiel Algorithmus aus einem der früheren Videos. Das ist Selection Sort und wir sehen
- Selection Sort ruft argmin auf und das habe ich jetzt nicht hingeschrieben, aber argmin ruft nicht wieder Selection Sort auf und auch nicht sich selbst.
- Also argmin ist nicht rekursiv und Selection Sort ist deswegen auch nicht rekursiv. Das ist ein einfacher iterativer Algorithmus. Hier unten nun zum Vergleich der selbe Algorithmus,
- aber anders hingeschrieben, nämlich ohne Schleife, dafür rekursiv. Sie sehen hier ruft der Algorithmus wieder Selection Sort auf, sich selbst, allerdings mit einer anderen Eingabe.
- Die Eingabe hier sieht so aus, dass wir das Array ab einer bestimmten Position i bekommen. Das ist am Anfang vielleicht 1 und dann, wenn wir es hier das nächste Mal aufrufen,
- ist das 1 plus 1 also 2 und wenn das innerhalb dieses Aufrufs wieder der nächste Aufruf kommt, steht hier 2 plus 1 also 3 und so weiter. Durch diese Rekursion wird sozusagen diese
- Schleife hier anders formuliert und das Ganze muss irgendwann abbrechen und das passiert dann hier, wenn das i nämlich gleich n wird, bricht es ab und das ist exakt das gleiche,
- was ja in der Schleife auch passiert. Dies hier unten ist also ganz einfach, derselbe Algorithmus wird hier oben nur anders hingeschrieben, nämlich rekursiv.
- Bei allen rekursiven Algorithmen gibt es zwei Dinge. Zum einen haben alle rekursiven Algorithmen einen rekursiven Aufruf und das zweite Kennzeichen ist, es gibt immer eine
- Abbruchbedingung, eine Stelle, an der geprüft wird, ob ein nächster rekursiver Aufruf gemacht werden soll oder nicht. Jeder rekursive Algorithmus hat erstens einen rekursiven,
- mindestens einen rekursiven Aufruf, es gibt auch Algorithmen mit mehreren rekursiven Aufrufen und das wären dann auch rekursive Algorithmen. Zweitens aber muss auch immer
- eine Abbruchbedingung da sein und der Grund ist einfach, wenn sie nicht da ist, läuft die Rekursion ja immer und immer und immer wieder durch und dann hält der Algorithmus nicht an.
- In den allermeisten Fällen wird bei einem rekursiven Algorithmus der rekursive Aufruf ein wenig anders aussehen als der ursprüngliche Aufruf. Wir sehen hier einen Unterschied in den
- Argumenten und wenn das nicht so ist, kann eventuell der Algorithmus sinnvoll sein, wir machen kurz ein Beispiel, aber meistens ist er das nicht. Der Algorithmus ist ein
- bisschen sinnlos, er ist nur dazu da, um zu illustrieren, was ich hier meine. Warten auf Godot hat überhaupt kein Argument, er wird trotzdem ein rekursiver Algorithmus sein.
- Wenn nämlich Godot da ist, dann sind wir fertig mit dem Waden und dann können wir Return sagen und Hurra zurückgeben, weil Godot endlich da ist. Und ansonsten warten wir weiter und das können
- wir einfach so machen, indem wir wieder warten auf Godot aufrufen. Nun haben wir hier einen Algorithmus, der immer wieder weiter läuft bis endlich Godot da ist und wenn Sie das Theaterstück
- kennen, Godot kommt nie. Bei manchen Algorithmen haben sie sowohl eine Abbruchbedingung als auch immer wieder andere Argumente bei dem Aufruf und trotzdem halten die Algorithmen nicht an.
- Darauf müssen Sie also weiterhin achten, ob ein Algorithmus anhält oder nicht. Hier ein einfaches Beispiel. Der Algorithmus, und ich nenne ihn gleich, hält trotzdem nicht,
- weil der hält trotzdem nicht, bekommt eine ganze Zahl als Argument. So und der Algorithmus soll jetzt eine Abbruchbedingung haben, die schreibe ich gleich mal hin.
- Wenn das n nämlich gleich 32 ist, dann halten wir an und geben eben das n zurück. Und ansonsten machen wir einen rekursiven Aufruf und dann geben wir eben zurück. Hält trotzdem
- nicht von n minus eins. Ja, den Algorithmus hier unten kennen Sie schon aus einem anderen Video. Das ist der Algorithmus, nachdem der Schneider von Schilder seine Hosen
- kürzt. Und es ist schon klar, wenn wir hier mit einer Zahl kleiner als 32 reinkommen, dann läuft das immer und immer weiter. Der Algorithmus würde nicht anhalten. Und wenn
- Sie das implementieren als ein Programm, welche Art Fehler bekommen Sie dann? Sie bekommen tatsächlich einen Fehler zurück. Das Programm wird nämlich angehalten vom
- Betriebssystem und die Fehlermeldung, die Sie bekommen, heißt Stack Overflow. Die Fehlermeldung Stack Overflow gibt uns einen Hinweis darauf, dass bei realen Maschinen die
- Anzahl der rekursiven Funktionsaufrufe, oder überhaupt der Funktionsaufrufe, die Wiederfunktionen aufrufen und so weiter, dass die begrenzt ist. Das heißt, man kann nicht unendlich
- oft wieder innerhalb einer Funktion wieder eine aufrufen und wieder eine und so weiter. Die Rekursionstiefe ist begrenzt bei realen Maschinen. Und wenn wir diese
- Grenze überschreiten, kriegen wir eben diese Fehlermeldung. Nun fehlt eben schon der Begriff Rekursionstiefe und den wollen wir kurz definieren. Das ist ganz klar,
- der erste Aufruf, der soll die Rekursionstiefe 1 haben. Man könnte auch 0 sagen. Wir sagen jetzt einfach mal 1. Und dann, wenn wir einen Aufruf
- haben mit Rekursionstiefe i, dann haben alle rekursiven Aufrufe innerhalb dieses Aufrufes die Rekursionstiefe i plus 1. Wenn dann die Aufrufe mit Rekursionstiefe i plus 1 Wiederaufrufe machen
- haben, die natürlich Rekursionstiefe i plus 2 und so weiter und so weiter. Das heißt, je tiefer die Verschachtelung ist, desto größer wird diese Wert Rekursionstiefe.
- Und was Sie hier gerade sehen, ist nichts anderes als eine rekursive Definition eines Begriffs, nämlich des Begriffs, was Rekursionstiefe bedeutet. Nun ist meine Erfahrung,
- dass viele Studierende gerade in den ersten Semestern Rekursion nicht sonderlich mögen und der Grund dafür ist Rekursion macht einen Knoten ins Gehirn. Machen wir doch mal die Probe.
- Ich schreibe Ihnen jetzt hier einen Algorithmus auf und Sie müssen überlegen, was der denn ausrechnet. Der Algorithmus heißt Riddle, weil es eben ein Rätsel ist und er bekommt eine Zahl n.
- Das soll wieder eine natürliche Zahl sein und wir sagen mal, es darf aber auch eine Null dabei sein, also eine ganze nicht negative Zahl. Und dann kommt die Abbruchbedingung, wenn n gleich 0 ist,
- dann brechen wir ab und geben eine 1 zurück und ansonsten geben wir das zurück, was man bekommt, wenn man eine 2 mit dem Ergebnis des rekursiven Algorithmus aufruft, also Riddle von n minus 1.
- Ihre Aufgabe jetzt zu sagen, was ist denn Riddle von n, wenn man irgendein n einsetzt, was kommt denn dabei heraus. Dann machen wir mal ein paar Beispiele. Riddle von 0,
- das ist die Abbruchbedingung, das ist natürlich 1. Was ist denn Riddle von 1? Riddle von 1 ist, man geht hier rein und hat 2
- mal Riddle von 0 stehen. Das haben wir eben rausbekommen, das ist 1, also 2 mal 1 ist also gleich 2. Was ist Riddle von 2? Das ist 2 mal Riddle von 1.
- Riddle von 1 haben wir eben ausgerechnet, 2 mal 2 ist also 4. Machen wir noch eins. Ehe es langweilig wird, das ist 2 mal Riddle von 3, ist 2 mal Riddle von 2,
- ist also 2 mal 4, ist also 8 und das Muster ist ganz einfach. Riddle von n ist gleich 2 hoch n. In unseren Beispielen kommt das hin, 2 hoch 0 ist 1, also Riddle von 0 ist 2 hoch 0 ist 1, ist
- richtig. Und die anderen Beispiele funktionieren auch und es funktioniert immer und das kann man hier mit einem ganz einfache Induktionsbeweis zeigen. Es gilt eben für n gleich 1 und wenn
- es für n gleich i gilt, gilt es auch für n gleich i plus 1, weil wir einfach dann noch einen Faktor 2 dazu multiplizieren und damit funktioniert das Ganze. Nun wenn rekurriere
- Algorithmen dazu tendieren und Knoten ins Gehirn zu machen, gibt es dann vielleicht einen Trick, wie wir dafür sorgen können, dass wir verstehen, was so ein Algorithmus macht.
- Und so ganz so ein Trick gibt es nicht, aber es gibt eine Faustregel und das ist, wie ich sie nenne, die Bossmethode und da werden wir noch einmal im Video über Teilen und Herrschen
- drauf zu sprechen kommen. Wenn jetzt Rekursion so schwer ist, bringt es dann wenigstens was? Können wir jetzt was Neues machen, was wir vorher nicht konnten? Und die Antwort heißt nein.
- Alles, was man rekursiv als Algorithmus formulieren kann, kann man auch ohne Rekursion machen. Also zu jedem rekursiven Algorithmus
- gibt es einen iterativen Algorithmus und der läuft sogar gleich schnell wie der rekursive Algorithmus und umgekehrt. Jeden iterativen Algorithmus kann ich ziemlich problemlos in einen
- rekursiven Algorithmus umwandeln. Von rekursiv zu iterativ kann manchmal ein bisschen knifflig sein. Da braucht man eventuell eine zusätzliche Datenstruktur, zum Beispiel so einen Stack,
- den Stack, der dann überfließen kann und dann Stack Overflow macht, zum Beispiel. Den muss man dann eventuell noch extra hinzufügen. Und da liegt der Grund, warum Rekursion
- manchmal nützlich ist. Man spart nämlich oft etwas, was man sonst hinschreiben muss. Es ist nützlich, es vereinfacht Dinge, insbesondere Dinge, wo man Sachen durchsucht,
- die ihrerseits wieder rekursiv sind. Was heißt das? Dinge durchsuchen, die rekursiv sind. Was sind denn rekursive Dinge?
- Zum Beispiel Bäume. Bäume kann man ganz leicht rekursiv definieren und so wird das im Allgemeinen auch gemacht. Was ist ein Baum? Ein Baum ist entweder so etwas,
- er besteht nur aus einem einzelnen Blatt, was dann gleichzeitig die Wurzel ist, oder ein Baum ist ein Wurzelknoten, der dann ein oder mehrere Kinder hat und die sind wieder Bäume.
- Und Sie sehen, warum ist diese Definition rekursiv? Na, weil das Ganze ja eine Definition für Baum sein soll, aber in der Definition kommen wieder Dinge,
- die wieder ihrerseits Bäume sind. Wie ist das möglich? Es ist deswegen möglich, weil es eine Art Abbruchbedingungen für diese Art Rekursion gibt und die ist hier vorne.
- Letztlich können alle Bäume auch irgendwann einmal Kinder haben, die Blätter sind. Mit solchen Bäumen hat man es in der Informatik oft zu tun, auch da wo man vielleicht nicht
- damit rechnet. Nehmen wir mal als Beispiel, wir wollen ein Verzeichnis durchsuchen, auf Englisch, ein Directory. Sie wissen, so ein Verzeichnis besteht aus Dateien, die dort drin stehen und
- eventuell sind dort weitere Verzeichnisse drin und das ist genau das gleiche, was wir hier haben. Wir haben Dateien und dann haben wir rekursiv wieder andere Verzeichnisse und in diesen
- Verzeichnissen können wieder andere sein und wenn Sie das durchsuchen wollen und zwar über alle Verschachtelungstiefen hinweg, dann suchen Sie am besten rekursiv. Das bietet sich an,
- weil die Datenstruktur, die Sie durchsuchen, rekursiv ist. Wenn also unser Algorithmus, den wir hier SearchDir, nennen, das Verzeichnis Dir untersuchen soll und zwar rekursiv,
- dann muss er durch alle Einträge in diesem Directory durchlaufen. Das machen wir zum Beispiel mit so einer Schleife, also für alle Einträge im Directory.
- Wir machen Folgendes, wir prüfen nach, ist denn ein File ein Directory und wenn das der Fall ist, dann müssen wir rekursiv das Directory ebenfalls durchsuchen und wenn nicht,
- dann können wir zum Beispiel diese Datei ausgeben und sind dann fertig. Das hier unten entspricht dann der Abbruchbedingungen. Sobald Sie ein Verzeichnis finden, wo Sie überhaupt kein
- Unterverzeichnis mehr haben, dann kommen Sie nur in diesen zweiten Fall und dann endet das Ganze ohne weitere Rekursion. Der Algorithmus, den Sie hier sehen, ist im Übrigen ein Beispiel für eine
- Technik, mit der wir uns später in einem anderen Video noch ganz intensiv beschäftigen wollen. Das ist nämlich eine sogenannte Tiefensuche, genauer eine Postorder-Tiefensuche. Natürlich
- können Sie diesen Algorithmus auch irgendwie iterativ hinschreiben. Alles, was man rekursiv hinschreiben kann, kann man auch iterativ hinschreiben, wie wir
- schon gesagt haben. Aber es ist so einfach viel schöner und viel klarer zu verstehen. Darum ist Rekursion so nützlich.
Zum Nachlesen
RekursionAls Rekursion (lateinisch recurrere ‚zurücklaufen') wird ein prinzipiell unendlicher Vorgang bezeichnet, der sich selbst als Teil enthält oder mithilfe von sich …
InformatikAls einfache Rechengeräte leisteten Abakus und später der Rechenschieber unschätzbare Dienste. 1641 konstruierte Blaise Pascal eine mechanische …