► Hacking mit Python https://amzn.to/3pxVnmh (*) ► Mein Python-Buch https://amzn.to/3ARMbw8 (*) ► Ethical Hacking mit ChatGPT https://amzn.to/3Qf9mID (*) Als Amazon-Partner verdiene ich an qualifizierten Verkäufen. Bei den Amazon-Links (https.//amzn.to/???????) handelt es sich um Affiliate-Links. Wenn du etwas über diesen Link kaufst, bekomme ich eine kleine Provision. Der Preis ändert sich nicht, wenn du über diesen Link einkaufst. Vielen Dank für deine Unterstützung.
Inhalt 📚 In diesem Video zeige ich dir anhand eines einfachen Beispiels, was man unter Rekursion versteht. Du lernst, wie eine Rekursion Schritt-für-Schritt abläuft und wie du sie dir vorstellen kannst. #Rekursion#Informatik#Unterricht
00:00 | Die Fakultätsfunktion 01:03 | Implementierung der Fakultätsfunktion (ohne Rekursion) 02:23 | Rekursive Definition der Fakultätsfunktion 05:08 | Rekursive Implementierung der Fakultätsfunktion 05:33 | Veranschaulichung der Rekursion
in diesem Video zeige ich dir anhand
eines einfachen Beispiels was man unter
Rekursion versteht du lernst wie eine
Rekursion Schritt für Schritt abläuft
und wie du sie dir vorstellen kannst
dazu schauen wir uns die sogenannte
fakultätsfunktion an die kennst du schon
aus der Schule wenn du dich mit
Stochastik beschäftigt hast dre Fakultät
das wird mit einem Ausrufezeichen hinter
der dre dargestellt bedeutet 3* 2 x 1
also 6 vier Fakultät
4* 3* 2* 1 also 24 5 Fakultät ist 5* 4*
3* 2* 1 also 120 und so weiter
allgemeinilt n Fakultät ist n mal n- 1
mal n- 2 und immer so weiter mal 3 x 2 x
1 beachte dass nullfakultät als 1
definiert ist und ein Fakultät wieder
eins ergibt schauen wir uns zuerst
einmal an wie man die fakultätsfunktion
in Python ohne Rekursion implementiert
wir nennen sie Fakultät und übergeben
ihr als Parameter den Wert n für den wir
n Fakultät berechnen wollen in einer
Variable namens Ergebnis wird später das
Ergebnis endfakultät gespeichert wir
initialisieren diese Variable mit dem
Wert 1 und nicht 0 damit wir bei der
Multiplikation nicht immer bei Null
landen danach laufen wir in einer
vorschleife nacheinander alle Zahlen von
N bis 1 ab und multiplizieren Sie mit
dem aktuellen Wert der Variable Ergebnis
beachte dass wir in der rangeefunktion
als Startwert n angeben und dann
rückwärts daher die -1 laufen bis zum
Endwert 1 dieser wird nicht mit
berücksichtigt das heißt wir laufen
quasi bis inklusive 2 aber das ist nicht
schlimm weil eine Multiplikation mit 1
ändert ja nichts zum Schluss geben wir
das Ergebnis mit einer returnanweisung
zurück um unser Programm zu testen rufen
wir es exemplarisch mit dem Parameter n
= 3 auf als Ergebnis erhalten wir 3* 2*
1 also 6 wenn wir n= 5 übergeben
erhalten wir 5 x 4 x 3 x 2 x 1 das
kennst du schon also
120 okay das war der einfache Teil jetzt
volle Konzentration wir versuchen uns an
dem rekursiven Ansatz
Rekursion ist ein Konzept in der
Programmierung bei dem eine Funktion
sich selbst aufruft das heißt unsere
Funktion Fakultät wird innerhalb der
Funktion selbst noch mal aufgerufen
dieser Ansatz ist besonders nützlich für
Probleme die sich in kleinere
gleichartige Probleme zerlegen lassen
der Grundgedanke hinter der Rekursion
besteht darin ein Problem seit zu
verkleinern bis ein einfacher oder
bekannter Fall erreicht wird der direkt
gelöst werden kann dieser Fall wird als
basisfall bezeichnet jetzt wenden wir
diesen Gedanken mal auf unsere
fakultätsfunktion an der basisfall ist
der bereits eingangs erwähnte Fall 1
Fakultät = 1 weil der ist relativ
einfach zu berechnen und der gibt einen
konkreten Wert zurück ohne dass wir
rekursiv erst auf diesen Wert kommen
müssen wir könnten hier auch
nullfakultät g=ich 1 nehmen doch wir
entscheiden uns aus
anschaulichkeitsgründen für ein Fakultät
ist GLE 1 für den basisfall so und jetzt
kom wir zu der eigentlichen Rekursion
denn wir haben ja vorhin bei der
Definition der Fakultät gesagt n
Fakultät ist n mal n- 1 mal n- 2 mal und
immer so weiter mal 3 x 2 x 1 das können
wir auch anders notieren indem wir sagen
nfakultät ist n mal n- 1 Fakultät okay
warum gilt das na ja n- 1 Fakultät ist
dir wiederum n- 1 mal n- 2 mal n- 3 und
immer so weiter wer hier sozusagen die
fakultätsfunktion auf der linken und auf
der rechten Seite stehen und dadurch
dass es auf der rechten Seite steht
rufen wir diese fakultätsfunktion ja
quasi noch mal auf also wir definieren
das ganze rekursiv die Rekursion findet
hier also bei
n-1 Fakultät startatt hier rufen wir
dann auch später unsere Funktion
Fakultät quasi noch mal auf nur dass wir
diesmal n-1 statt n übergeben schauen
wir uns am besten mal ein Beispiel an
indem wir dre Fakultät rekursiv
berechnen zuerst berechnen wir dre
Fakultät durch 3 x 3- 1 Fakultät also 3
x 2 Fakultät genauso wie es bei der
rekursiven Definition der Fall ist auf
dieselbe Art berechnen wir nun z
Fakultät nämlich durch 2* 2- 1 Fakultät
also 2 x 1 Fakultät insgesamt ergibt
sich also 3 x 2 x 1 Fakultät ein
Fakultät ist der basisfall und da gibt
ein das heißt wir haben insgesamt 3* 2*
1 also 6 und genauso implementieren wir
jetzt auch die Funktion Fakultät
rekursiv wenn n = 1 ist dann haben wir
den basisfall erreicht und geben einfach
eins als konkreten Wert zurück ansonsten
folgen wir unserer rekursiven Definition
und berechnen n* N - 1 Fakultät indem
wir n - 1 unserer fakultäts Funktion
übergeben und das war es schon kurz und
schmerzlos ich möchte Dich jetzt aber
nicht mit den vermutlich noch auf der
Stirm verbliebenen Fragezeichen aus
diesem Video entlassen und erkläre dir
noch anschaulich wie beispielsweise das
Ergebnis von drei Fakultät mit unserer
Funktion Fakultät berechnet wird zuerst
wird die Funktion Fakultät mit dem Wert
n = 3 aufgerufen da n noch nicht eins
ist und der basisfall somit noch nicht
erreicht wurde betreten wir den den
erzzweig und rufen die Funktion Fakultät
jetzt noch mal mit n-1 also 2 auf jetzt
betreten wir wieder die
fakultätsfunktion und auch hier wurde
der basisfil noch nicht erreicht weshalb
wir erneut den erzzweig betreten und die
Funktion Fakultät mit dem Wert n- 1
sprich 1 aufrufen jetzt betreten wir
wieder die fakultätsfunktion und diesmal
haben wir den basisfall erreicht denn
wir haben ja im vorherigen Schritt
einsübergeben das heißt g geben eins als
konkreten Wert zurück dieser Wert wird
nun an den vorherigen rekursiven Aufruf
quasi hochgereicht und dieser gibt dann
2 x 1 also 2 zurück 2 wird ein den
darüberliegenden rekursiven Aufruf
hochgereicht und dort wird dann 3* 2
also 6 berechnet und zurückgegeben jetzt
sind wir beim initialen Aufruf angelangt
und dort wird sech zurückgegeben weil
das ist ja das Ergebnis was von dem
vorherigen Schritt hochgereicht wurde
und genauso würde das jetzt auch mit
allen anderen Werten für n passieren
versuche diesen Aufruf den ich dir hier
gezeigt habe mal schrittweise mit N = 5
nachzuvollziehen solltest du weitere
Fragen haben kannst du sie gerne unten
in den Kommentaren posten vielen Dank
fürs zusehen und bis zum nächsten Video