Aus Das deutschsprachige Scratch-Wiki
Man spricht von Rekursion, wenn ein Programm sich selbst in sich selbst aufruft. Dank der Weiteren Blöcke ist dies auch in Scratch möglich.
Grundsätze der Rekursion
Ein gutes Beispiel, um die Rekursion zu veranschaulichen ist die Fakultät. Man wendet die Fakultät bei der Wahrscheinlichkeitsrechnung an.
Erklärung von Fakultät
Ein Beispiel: Wir haben 3 freie Plätze und 3 Schilder, A,B und C.
Es gibt nun 6 verschiedene Möglichkeiten, wie diese Schilder angeordnet werden könnten: ABC, ACB, BAC, BCA, CAB und CBA. Dies lässt sich mit der Fakultät berechnen:
3! (gesprochen:Fakultät von 3) wäre 3*2*1, was 6 ergibt.
Doch genauer betrachtet ist 3!=3*2!. 2! ist dann 2*1!, und 1! ist gleich 1.
Alles folgt also der Formel n!= n*(n-1)!.
Anwendungsbeispiel
Probieren wir das noch einmal an einem Beispiel, 4!:
- 4!=4*3! — Um jetzt auf ein Ergebnis zu kommen, müssen wir 3! ausrechen
- 3!=3*2! — Nun dasselbe mit 2!
- 2!=2*1! — Nun mit der 1.
- 1!=1 — Hier stoppt alles
Wir können nun die vorherigen Ergebnisse lösen, wenn wir jetzt den ganzen Weg zurück rechnen:
- 1!=1*1 — also 1
- 2!=2*1 — also 2!=2
- 3!=3*2 — also 6
- 4!=4*6 — also ist 4!=24
Um also auf ein Ergebnis zu kommen, müssen wir uns eine Rechnung merken und eine Teilaufgabe ausrechen, die eventuell wieder unterteilt werden muss, bis wir schließlich 1! haben, welche ein eindeutiges Ergebnis hat.
Fakultät in Programmen
Programmtechnisch gesehen, haben wir eine Rechnung, welche n*(n-1)! berechnet. Darin enthalten ist jedoch das gleiche Programm nochmal, welches (n-1)! ausrechnen muss. Die unlösbaren Rechnungen bleiben im Arbeitsspeicher solange gespeichert, bis sie ihre Teilaufgabe, n!, gelöst bekommen. Doch das ist auch gleichzeitig die Gefahr bei der Rekursion. Nehmen wir zum Beispiel Zahlen über 1000!, würde das Programm abstürzen, da es tausende von Teilaufgaben zwischenspeichern muss.
Rekursion in Scratch
Versuchen wir in Scratch einen Fakultätsrechner zu programmieren.
Wir brauchen dafür einen eigenen Block, den wir "berechne ! von" nennen.
Nun folgt ein "number input", den wir "n" nennen.
Jetzt bearbeiten wir den Kopfblock, welcher das Skript definiert.
Wir beginnen mit einem Falls-Sonst-Block. Dort wird geprüft, ob n (aus dem Kopf-Block) = 0 ist. Das ist nur der Fall, wenn wir 0! haben.
Jetzt muss dort die Abbruchbedingung geschaffen werden, das heißt dieser Block löst seine Teilaufgabe, um die Lösung aller Teilaufgaben zu ermöglichen.
Dazu brauchen wir die Variable "ergebnis".
Falls die Bedingung stimmt, wird ergebnis auf 1 gesetzt.
Falls nicht, muss der Block sich selbst aufrufen. Also steht dort: berechne ! von (n-1).
Dann wartet dieser Block, bis irgendwann ein neu aufgerufener Block ergebnis auf 1 setzt.
Dann folgt die Zeile: setze ergebnis auf (n * ergebnis).
So lösen sich alle Teilaufgaben auf und hinterlassen das gewünschte Ergebnis.
Der fertige Fakultätsrechner sollte dann so aussehen:
Stapelspeicher und Rekursion
Bei der Programmierung einer Rekursion ist darauf zu achten, dass man eine Variable in unterschiedlicher Rekursionstiefe mehrfach überschreibt. Ein Stapelspeicher bietet hier eine Möglichkeit um dies zu verhindern.
Beispiel: Fibonacci-Zahlen
Die Fibonacci-Zahlen sind eine unendliche Folge von natürlichen Zahlen, bei denen sich die nächste Zahl jeweils aus der Summe der beiden vorherigen ergibt.
Dadurch ergibt sich die Zahlenfolge (0),1,1,2,3,5,8,13,21,...
(Umfassende Informationen zur Fibonacci-Folge findest du im entsprechenden Wikipedia-Artikel)
Die Berechnung kann mit Hilfe einer Rekursion wie folgt ausgeführt werden:
Definiere Fibonacci (n) //gibt die n-te Fibonaccizahl auf dem Stack zurück falls <(n)<(2)>, dann füge (n) zu [Stapel v] hinzu stoppe [dieses Skript v] sonst Fibonacci ((n)-(1)) //berechne und lege Antwort auf Stapel Fibonacci ((n)-(2)) //berechne und lege Antwort auf Stapel setze [tmp1 v] auf (Element (Länge von [Stapel v]) von [Stapel v]) //Hilfsvariable lösche (Länge von [Stapel v]) aus [Stapel v] setze [tmp2 v] auf (Element (Länge von [Stapel v]) von [Stapel v]) //Hilfsvariable lösche (Länge von [Stapel v]) aus [Stapel v] füge ((tmp1)+(tmp2)) zu [Stapel v] hinzu Wenn die grüne Flagge angeklickt Fibonacci (7) //berechne die 7te Fibonaccizahl setze [tmp1 v] auf (Element (Länge von [Stapel v]) von [Stapel v]) sage (tmp1) für (2) Sekunden //probiere aus was hier rauskommt!
Beispiel Rekursion mit Stapelspeicher und lokalen Variablen
Das folgende rekursive Programm soll die Anzahl der Möglichkeiten ausrechnen um eine Zahl als verschiedene Summe von positiven Zahlen darzustellen.
Beispiel:
2=1+1 (2 Möglichkeiten) 3=2+1=1+1+1 (3 Möglichkeiten) 5=4+1=3+1+1=2+1+1+1=1+1+1+1+1=3+2=3+1+1 (7 Möglichkeiten)
Das folgende Programm enthält einen rekursiven Algorithmus zum Berechnen der Möglichkeiten, aber es funktioniert nicht richtig.
Definiere summen (zahl) (stueck) //dieses Skript tut nicht was es soll! setze [i v] auf (1) falls <(zahl) < (stueck)>, dann setze [s v] auf (zahl) sonst setze [s v] auf (stueck) ende wiederhole bis <(s) < (2)> summen((zahl)-(s))(s) ändere [i v] um (ergebnis) ändere [s v] um (-1) ende setze [ergebnis v] auf (i) Wenn die grüne Flagge angeklickt summen (5)(5) //Beispiel für die Zahl 5 sage (ergebnis) für (2) Sekunden
Für die Zahl 5 sollte hier ja 7 herauskommen, aber das Programm meldet nur 2 zurück. Der Fehler liegt daran, dass die Variablen i und s von allen rekursiv aufgerufenen Unterprogrammen benutzt werden. Damit die Variablen ihren Wert auch nach dem Aufruf einer Rekursion behalten, empfiehlt sich das Zwischenspeichern der beiden Variablen in einem Stapelspeicher.
Das korrekte Programm sieht nun so aus:
Definiere summen (zahl) (stueck) füge (i) zu [Stapel v] hinzu //Sichern der Werte von i und s auf dem Stapelspeicher füge (s) zu [Stapel v] hinzu setze [i v] auf (1) falls <(zahl) < (stueck)>, dann setze [s v] auf (zahl) sonst setze [s v] auf (stueck) ende wiederhole bis <(s) < (2)> summen ((zahl)-(s)) (s) ändere [i v] um (ergebnis) ändere [s v] um (-1) ende setze [ergebnis v] auf (i) setze [s v] auf (Element (Länge von [Stapel v]) von [Stapel v]) //Zurückholen der Variablenwerte in umgekehrter Reihenfolge lösche (Länge von [Stapel v]) aus [Stapel v] setze [i v] auf (Element (Länge von [Stapel v]) von [Stapel v]) lösche (Länge von [Stapel v]) aus [Stapel v] Wenn die grüne Flagge angeklickt summen (5) (5) //Beispiel für die Zahl 5 sage (ergebnis) für (2) Sekunden
In folgendem Projekt findest du die oben vorgestellten Codebeispiele:
[wiki=de:Rekursion]Rekursion[/wiki]
