Rekursion Informatik=> unverständliches Beispiel?
Hey,
Ich verstehe diesen Sachverhalt nicht. Warum ist n=4 und warum rechnen wir 2* rekursiv()?
Also warum die 2*?
Und wie kommt man bei 2*rekursiv(3) auf 2*2*2*2?
Ich verstehe das ganze Schaubild unten nicht.
Über Antworten würde ich mich sehr freuen!
4 Antworten
Da du sagt, das ganze Schaubild nicht zu verstehen, will ich versuchen, dir eine sehr ausführliche Erklärung zu geben. Das Schaubild ist nämlich sehr clever gemacht und er klärt dem, der es versteht, wirklich alles.
Beschreibung des Schaubilds:
Das gelbe Kästchen oben links enthalt eine Wertzuweisung an die Variable n. Die Variable n erhält den Wert 4. Das Kästchen entspricht der Zeile 8 des gezeigten Programms. Dort haben wir den Befehl input, der eine Eingabe von der Konsole liest. Die eingelesene Eingabe wird mit einem Aufruf von int() in eine ganze Zahl umgewandelt und das Ergebnis der Variablen exponent zugewiesen. Dass die Variable im Programm exponent genannt wird und im Schaubild n, ist als Schlamperei zu rügen. In Unterrichtsmaterial für Anfänger sollten derartige Unstimmigkeiten nicht vorkommen.
Das Schaubild ist zweigeteilt: Links sehen wir gelbe Kästen und rechts rote Kästchen. Die Kästchen sind miteinander durch Pfeile verbunden, die den Ablauf der Rechnung zeichen. Du gehst also von dem Startpfeil aus, der links nebem dem zweiten Kästchen von oben steht und folgst dann den Pfeilen, bis du zu dem roten Kästchen rechts oben kommst, von dem kein Pfeil mehr abgeht.
Jedes gelbe Kästchen bedeutet einen Funktionsaufruf und jedes rote Kästchen die Weiterverarbeitung eines von einer Funktion erhaltenen Werts. Genauer: Ein gelber Pfeil bedeutet einen Funktionsaufruf und ein roter Pfeil die Ausführung eines return-Befehls.
Der Aufruf im Kästchen mit dem Startpfeil steht im Programm in Zeile 9 und dort nach dem Zuweisungszeichen "=".
Der Aufruf führt dich in die in den Zeilen 1 bis 5 definierte Funktion, die mit dem Wert 4 aufgerufen wird. Ind er Funktion hat der Parameter e also den Wert 4. In der Funktion wird in einer Fallunterscheidung festgestellt, dass der Wert von e nicht 1 ist; folgerichtig wird mit der Berechnung des Ausdrucks begonnen, der in Zeile 5 dem Schlüsselwort return folgt .
Für die Weiterführung der Rechnung gehen wir dem Pfeil folgend ins nächste gelbe Kästchen. Da steht jetzt erstmals ein rekursiver Aufruf, aber nicht nur das: Es steht dort der vollständige Ausdruck, der dem Schlüsselwort return folgt. Diese Schreibweise erinnert uns daran, dasswir, sobald wir das Ergebnis von rekursiv(3) erhalten haben, noch eine Multiplikation mit 2 ausführen müssen, bevor der return-Befehl ausgeführt werden kann.
Wenn du den weiteren gelben Pfeilen folgst, siehst du, wie weitere rekursive Aufrufe erzeugt werden. Schließlich bewirkt der Aufruf rekursiv(1) das Ende der Rekursion: Die Funktion wird in Zeile 3 mit dem Eregebnis 2 verlassen. Das ist die Situtation, die durch das rote Kästchen ganz unten in der Mitte dargestellt wird.
Wenn du den weiteren roten Pfeilen folgst, siehst du, wie die rekursiven Aufrufe der Funktion einer nach dem anderen abgeschlossen wird, wobei das erhaltene Ergebnis immer mit dem Faktor 2 multipliziert wird, bevor die return-Anweisung ausgeführt wird.
Den rekursiven Abstieg bis zum Aufruf rekursiv(1) hast du richtig verstanden und es ist dir auch klar, dass dann die Bedingung e == 1 erfüllt ist und deshalb sogleich der Wert 2 zurückgegeben wird.
Wenn der Auruf rekursiv(1) beendet ist, sind aber noch alle früheren rekursiven Aufrufe unfertig, und die werden dann nacheinander fertiggestellt. Die schrittweise Fertigstellung von rekursiv(2), sodann rekursiv(3) und zum Schluss rekursiv(4) wird durch die roten Kästchen veranschaulicht. Die in den roten Kästchen angegebenen Rechenoperationen werden in der Reihenfolge ausgeführt, die durch die roten Pfeile festgelegt ist.
In dem Diagremm erklärt ein rotes Kästchen immer die Fertigstellung des Aufrufs, der durch das links auf gleicher Höhe stehende gelbe Kästchen begonnen wurde. Das habe ich vielleicht nicht deutlich genug gesagt.
Zur Basis:
Das Beispielprogramm ist hier leider in keiner Hinsicht vorbildlich. In Zeile 7 wird der Variablen basis der Wert 2 zugewiesen. Das sieht nett aus, aber da die Variable im ganzen Programm nicht ein enziges Mal in einer Formel erscheint, ist das völlig nutzlos. Du könntest die Zeile 7 streichen ohne dass sich am Programm etwas ändert. Die Basis der Potenz, die berechnet werden soll, ist stattdessen inden Zeilen 3 und 5 als Konstante 2 ausgeschrieben. WEnn du in den Zeilen 3 und 5 die Zahl 2 durch die Zahl 3 ersetzen würden, würde die Funktion recursiv dir Potenzen von 3 berechnen und wenn du die beiden Vorkommen der Zahl 2 durch die Zahl 12 ersetzt, berechnet die Funktion dir Potenzen von 12.
-----------------------------------------------------------------------------------------
Warum ist rekursiv(4) das Gleiche wie 2*rekursiv(3)?
Das liegt an der folgenden Formel, die dir zwar sicher bekannt ist, an die du aber natürlich nicht jeden Tag denkst:
n n-1
2 = 2 * 2 wo n eine natürliche Zahl ist
Die Formel gibt natürlich nicht nur für die Basis 2, sondern für jede Basis.
Wenn wir voraussetzen, dass rekursiv(n) die Potenz 2^n berechnet, dann können wir tatsächlich im Rumpf der Funktion schreiben, dass wir die Potenz berechnen, indem wir das Ergebnis von rekursiv(n-1) (also die Potenz 2^(n-1)) nochmals mit der Basis 2 multiplizieren. Damit ist auch deine letzte Frage "Warum machen wir diese 2*?" beantwortet.
Vielen vielen Dank!!! Hoffentlich kommt so eine Aufgabe nicht in meinem Test dran😂
Wie andere Foristen und auch ich schon bemerkt haben, sit das Programm alles andere als vorbildlich geschrieben. Wenn man die Basis außerhalb des Funktionskörpers als Variable zur Verfügung stellen will, muss man das so schreiben:
def rekursiv(e):
global basis # sehr wichtig!
if e == 1:
return basis
else:
return basis * rekurisv(e - 1)
basis = 2
exponent = int(input("Gib den Exponenten ein: "))
ergebnis = rekursiv(exponent)
print(str(ergebnis))
Ausschlaggebend wichtig ist hier die 2. Zeile, in der basis als globale Variable vereinbart wird. Globale Variablen sind aber ein sehr spezielles Thema, das in Python-Kursen meist erst ziemlich spät und manchmal auch überhaupt nicht behandelt wird.
Wenn man diese ominöse globale Variable vermeiden will, kann man schreiben:
def rekursiv(e):
basis = 2
if e == 1:
return basis
else:
return basis * rekurisv(e - 1)
exponent = int(input("Gib den Exponenten ein: "))
ergebnis = rekursiv(exponent)
print(str(ergebnis))
Jetzt ist basis eine lokale Variable der Funktion. Diese lokale Variable wird in jedem rekursiven Aufruf neu erzeugt, was auch nicht ds Gelbe vom Ei ist, aber immerhin ist es jetzt möglich, den Wert der Basis an einer Stelle im Progrmm niederzuschreiben.
Das Programm hat im übrigen noch andere Auffälligkeiten: Wenn du bei der Eingabeauffoderung"Gib den Exponenten ein: " den Wert 0 oder eine negative ganze Zahl eingibst, bricht die Rekursion nie ab! Das ist ärgerlich, denn das Programm versagt dann katastrophal, sobald kein Speicher mehr für weitere rekursive Aufrufe zur Verfügung steht.
Da das Programm alles andere als ein Meisterwerk ist, wäre dein Lehrer sehr gut beraten, eine Unterrichtsstunde zum Thema "Was mache ich gegen die Mängel in diesem Programm?" zu halten. Ausreichend Stoff für eine ganze Stunde hätte er.
Es gilt:
sowie
Genau dies benutzut die Rekursion.
Indem sie sich für 2^n-1 wieder selbst aufruft, bis sie eben 2^1 direkt lösen kann.
Das Schaubild zeigt das eben auf.
------
Was die Geschichte betrifft, die zeigt das gleiche Rekursionsprinzip an einem anderen Beispiel:
Ich hole einen Eimer für das n. Fach, Du mußt die n-1 Fächer befüllen. Analog: Ich führe die letze Multiplikation für 2^n aus, wenn Du mir das Ergebnis für n-1 ausgerechnet hast.
Die Geschichte erklärt erstmal nur Rekursion und hat nix mit dem Codebeispiel zutun. Das Codebeispiel ist auch ungünstig, weil es die 2 da einfach fest drin stehen hat. Eigentlich hätte hier denke ich die Variabel basis verwendet werden sollen und als Variabelnamen für e hätte man auch exponent nehmen sollen, sofern der Funktionsname nicht klar sagt worum es geht.
Letztlich rechnest du nur eine Hochzahl mit der Basis 2 aus. Sprich deine Aufgabe ist eigentlich mit dem Beispiel n = 4 quasi 2 hoch 4 auszurechnen.
Das kannst du natürlich machen indem du 2 * 2 * 2 * 2 ausrechnest. Du kannst das Problem aber auch in ein kleineres aufteilen:
2 * 2 * 2 * 2 ist eben das gleiche wie 2 * 2 hoch 3.
Und das Teilproblem 2 hoch 3 ist das gleiche wie 2 * 2 hoch 2
Und das Teilproblem 2 hoch 2 ist wieder das gleiche wie 2 * 2 hoch 1.
Und hoch 1 ist die Zahl selbst.
Du hast bei einer Rekursion immer eine Abbruchbedingung wie hier, wenn der Exponent e == 1 ist. Das ist der Punkt wo dein Program endet und die eigentliche Rechnung stattfindet.
Der Teil davor verkleinert dein Problem immer weiter in Teilprobleme. Du fängst also oben links an, verkleinerst dein Problem bis zur Abbruchbedingung 2 und dann gehst du hoch mit den Ergebnissen auf der rechten Seite.
2 * rekursiv(3) ist nicht direkt gleich 2*2*2*2
2 * rekursiv(3) = 2 * 2 * rekursiv(2) und so weiter.
Schau dir den Code an und überleg dir, wann und mit welchem Wert wieder selbst in die Funktion gesprungen wird
Aber woher kommt die 2*.... ist das einfach vorgegeben oder wie?
Ich kann das aus der Geschichte nämlich nicht ableiten.
Ja, die 2 ist vorgegeben. Die ist im Programm code festgelegt. Das Arbeitsblatt ist meiner Meinung nach schlecht gemacht. Wenn man in dem Code eine andere Basis reinspeichert, also da wo Basis = 2 steht z.B. Basis = 4 hinschreiben würde, dann hätte das keine Auswirkungen auf das Programm. Das würde die Potenz immernoch mit der Basis 2 berechnen. Außerdem sind die Namen der Variablen inkonsistent. Auf der linken Seite heißt die Variable e, und auf der rechten Seite heißt sie dann aufeinmal n
Ok. Ja, irgendwie ist alles so unverständlich. Deswegen hab ich das hier reingepostet. Also die Basis 2* ist einfach da, weil unten basis=2 steht, richtig?
Würde ich diese ändern auf 4, dann wäre es 4*? Oder?
Ansich hatte ich Rekursion verstanden (Funktion ruft sich selbst auf bis Abbruch), aber dieses Beispiel aus dem Unterricht macht mir zu schaffen. :')
Meinst du, wie ich z.B 10! in rekursiv schreiben würde? Das hab ich sogar verstanden 😂
"Also die Basis 2* ist einfach da, weil unten basis=2 steht, richtig?Würde ich diese ändern auf 4, dann wäre es 4*? Oder?" Das ist ja das dumme. In einem gut geschriebenen Programm würde es einen Unterschied machen, wenn man basis=4 hinschreiben würde. Aber in diesem Beispiel würde das Programm immernoch die Basis 2 nehmen, selbst wenn man unten basis=4 hinschreiben würde. Die 2 kommt daher, dass bei "else return 2* rekursiv (e -1)" steht. Wenn man das mit der Basis 4 machen würde, dann müste man im Programm code schreiben else return "4* rekursiv(e-1)"
Also rekursiv (4) wird in die Funktion gegeben... dann sehen wir, dass es größer als drei ist, also machen wir 2*rekursiv(3)
Dann rekursiv(3)>1 deswegen 2*rekursiv(2)
Rekursiv(2)>1 deswegen
2*rekursiv(1)
Rekursiv(1)==1
Deswegen wird return 2 ausgegeben und es wird beendet, richtig?
3 fragen noch:
1. Woran erkenne ich, dass es sich hierbei um 2^4 handelt? Die Basis haben wir in der Funktion doch nicht gegeben.
2. Muss man den roten Pfad machen oder dient das der Veranschaulichung?
3.Und ich versteh nicht, wie rekursiv(4) dasselbe sein kann wie 2*rekursiv(3)
Warum machen wir diese 2*?
Ansonsten vielen Dank schonmal!!!!