Wir nutzen Cookies, um das allgemeine Benutzerelebnis zu verbessern. Mit der Nutzung unseres Wikis stimmst du der Nutzung von Cookies zu.

Rekursion

Man spricht von Rekursion, wenn ein Programm sich selbst in sich selbst aufruft. Dank der Weiteren Blöcke ist dies jetzt 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*0!
  • 0!=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 0! 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)! Fakultät 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: Fakultät.png

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-Reihe

Die Fibonacci-Folge ist eine unendliche Folge von natürlichen Zahlen bei deren 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,...


Die Berechnung kann mit Hilfe einer Rekursion wie folgt ausgeführt werden:

Definiere push (element) //Block zur Implementierung eines Stapelspeichers
füge (element) zu [Stapel v] hinzu

Definiere pop (varname) //Block zur Implementierung eines Stapelspeichers
setze (varname) auf (Element (letztes v) von [Stapel v]) //um diesen Block einzugeben ist das JSON File zu editieren
lösche (letztes v) aus [Stapel v]

Definiere Fibonacci (n) //gibt die n-te Fibonaccizahl auf dem Stack zurück
falls <(n)<2> dann
push (n)
stoppe [dieses Skript v]
sonst
Fibonacci ((n)-(1)) //berechne und lege Antwort auf Stapel
Fibonacci ((n)-(2)) //berechne und lege Antwort auf Stapel
pop [tmp1] //Hilfsvariable
pop [tmp2] //Hilfsvariable
push ((tmp1)+(tmp2))

Wenn gf angeklickt
Fibonacci (7) //berechne die 7te Fibonaccizahl
pop [tmp1]
sage (tmp1) für (2) Sek. //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 gf angeklickt
summen (5)(5) //Beispiel für die Zahl 5
sage (ergebnis) für (2) Sek.

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 push (element) //Block zur Implementierung eines Stapelspeichers
füge (element) zu [Stapel v] hinzu

definiere pop (varname) //Block zur Implementierung eines Stapelspeichers
setze (varname) auf (Element (letztes v) von [Stapel v]) //um diesen Block einzugeben ist das JSON File zu editieren
lösche (letztes v) aus [Stapel v]

Definiere summen (zahl) (stueck)
push (i) //Sichern der Werte von i und s auf dem Stapelspeicher
push (s)
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)
pop [s] //Zurückholen der Variablenwerte in umgekehrter Reihenfolge
pop [i]

Wenn gf angeklickt
summen (5)(5) //Beispiel für die Zahl 5
sage (ergebnis) für (2) Sek.

In folgendem Projekt findest du die oben vorgestellten Codebeispiele:


112059659_144x108.png

Stapelspeicher


Code zum Einbinden ins Forum:
[wiki=de:Rekursion]Rekursion[/wiki]