Informatik 2 –

Rekursionen

©image: various

Prof. Dr. Alexander Hanuschkin

Outlook – Today

Heute Nächste Woche

• Iteration • XXX
• Rekursion
Fraktale [1]

• Ein Großteil der Natur aus Fraktalen aufgebaut.

• Beispiele aus der Natur sind z.B. Küstenlinien, Wolken oder Organe wie die Lunge.
• Das Wort „Fraktal“ wurde in den 1960er vom französischen
Mathematiker Benoit B. Mandelbrot eingeführt.
• Das Wort leitete es vom lateinischen Verb "frangere" und vom zugehörigen
Adjektiv "fractal" ab. Das Verb bedeutet brechen, Fragmente bilden.
• Sie stehen in enger Verbindung mit der sogenannten Chaostheorie.

[1] [Link]
[Link]
[Link]
Die wichtigsten Merkmale fraktaler Strukturen sind: [1]
1. Selbstähnlichkeit
Mandelbrots Definition:
"When each piece of a shape is geometrically similar to the whole,
both the shape and the cascade that generate it are called self-similar."

2. Skaleninvarianz
Absolutwerte sind irrelevant; ein Fraktal kann theoretisch
unendlich oft vergrößert werden, ohne dass eine
Veränderung der Form bemerkbar wird.

3. eine gebrochene Dimension:

Da das Fraktal nicht einen Teil der Ebene bzw. des Raumes voll ausfüllt* spricht
man von einer gebrochenen oder fraktalen Dimension, die nicht ganzzahlig ist.

[1] [Link]
[Link]
[Link]
Kochkurve

• Schwedischen Mathematiker Helge von Koch 1904

• Eines der Ersten formal beschriebenen fraktalen Objekte.
• Eines der am häufigsten zitierten Beispiele für ein Fraktal.
• Wurde bei der Entdeckung als Monsterkurve bezeichnet (überall
stetige, aber nirgends differenzierbare Kurve).
• Die Koch-Kurve ist auch in Form der kochschen Schneeflocke
bekannt, die durch geeignete Kombination dreier Koch-Kurven
entsteht.

[Link]
[Link]
[Link]
Kochkurve

• Schwedischen Mathematiker Helge von Koch 1904

• Eines der Ersten formal beschriebenen fraktalen Objekte.
• Eines der am häufigsten zitierten Beispiele für ein Fraktal.
• Wurde bei der Entdeckung als Monsterkurve bezeichnet (überall
stetige, aber nirgends differenzierbare Kurve).
• Die Koch-Kurve ist auch in Form der kochschen Schneeflocke
bekannt, die durch geeignete Kombination dreier Koch-Kurven
entsteht.

[Link]
[Link]
[Link]
Kochkurve

• Schwedischen Mathematiker Helge von Koch 1904

• Eines der Ersten formal beschriebenen fraktalen Objekte.
• Eines der am häufigsten zitierten Beispiele für ein Fraktal.
• Wurde bei der Entdeckung als Monsterkurve bezeichnet (überall
stetige, aber nirgends differenzierbare Kurve).
• Die Koch-Kurve ist auch in Form der kochschen Schneeflocke
bekannt, die durch geeignete Kombination dreier Koch-Kurven
entsteht.

[Link]
[Link]
[Link]
Kochkurve

• Schwedischen Mathematiker Helge von Koch 1904

• Eines der Ersten formal beschriebenen fraktalen Objekte.
• Eines der am häufigsten zitierten Beispiele für ein Fraktal.
• Wurde bei der Entdeckung als Monsterkurve bezeichnet (überall
stetige, aber nirgends differenzierbare Kurve).
• Die Koch-Kurve ist auch in Form der kochschen Schneeflocke
bekannt, die durch geeignete Kombination dreier Koch-Kurven usw..
entsteht.

[Link]
[Link]
[Link]
 Kochkurve

Python code siehe: [Link]

 Schneeflocke vs. kochschen Schneeflocke

Heute
• XXX

[Link]
66d6b4c6-50b5-4952-8c18-94f75e43fb36
 Schneeflocke vs. kochschen Schneeflocke

[Link]
66d6b4c6-50b5-4952-8c18-94f75e43fb36
 L-System „dreidimensionale Busch-ähnliche Pflanze“

Pflanzen sind sogenannte

Multifraktale, d.h. sie
besitzen auf
unterschiedlichen
Größenebenen bestimmte
verschiedene fraktale
Dimensionen [1].

[1] [Link]
Von Fraktalen zur Rekursion
• Als Rekursion (lateinisch recurrere ‚zurücklaufen‘) wird ein prinzipiell
unendlicher Vorgang, der sich selbst als Teil enthält oder mithilfe von
sich selbst definierbar ist, bezeichnet.
• „Der Begriff [Rekursion] ist sehr umfassend“.
In der Natur handelt es sich um einen häufig beobachtbaren Vorgang
(z. B. beim Pflanzenwachstum)
• Fraktale Muster werden oft durch rekursive Operationen erzeugt.
Auch einfache Erzeugungsregeln ergeben nach wenigen
Rekursionsschritten schon komplexe Muster.

• Bei der rekursiven Programmierung ruft sich eine Funktion in einem

Computerprogramm selbst wieder auf (d. h. enthält eine Rekursion).
Auch der gegenseitige Aufruf stellt eine Rekursion dar.
Unendlichfache Spiegelung als Beispiel für Rekursion

[Link]
[Link]
[Link]
Kurze Wiederholung Funktionen

Funktionen Beispiele

◼ Aufbau: ◼ Autowerkstatt
◼ Funktionsaufruf ◼ Auto mit Auftrag abgeben (Aufruf, Parameter)
◼ Funktionskopf (Prototyp, mit Argumenten) ◼ Arbeiten in der Werkstatt
◼ Funktionsrumpf ◼ Rückgabe Auto und Rechnung
◼ Rückgabewert
◼ Pizza liefern
◼ Bestellung
◼ Kochen
◼ Liefern
Iterative und rekursive Funktionen

◼ Iteration: Darunter versteht man das mehrmalige Ausführen einer Aktion. Hierzu nutzt man
Kontrollstrukturen wie Schleifen (for, while, …). Eine iterative Funktion hat also eine derartige
Kontrollstruktur im Funktionskörper.
➢ Kennen wir bereits!
◼ Rekursion: Darunter versteht man ebenfalls das mehrmalige Ausführen einer Aktion. Doch diesmal
nutzen wir keine Schleife, sondern die Funktion ruft sich selbst auf. Rekursive Funktionen sind
dadurch charakterisiert, dass diese
◼ Eine Abbruchbedingung brauchen
◼ Sich selbst aufrufen
➢ Algorithmen können sowohl iterativ als auch rekursiv formuliert werden
➢ Rekursionen lassen sich oftmals einfacher darstellen
➢ Iterationen sind oftmals effizienter, da das Zwischenergebnis der einzelnen Funktionsaufrufe nicht gespeichert
werden muss. Bei einer Rekursion müssen im Stack des Arbeitsspeichers die Zwischenergebnisse abgelegt
werden.
◼ Damit wir das besser verstehen können, schauen wir uns Beispiele an ..
Iterative und rekursive Funktionen (Beispiel)
◼ Rekursive Formulierung powRe()
𝒏
◼ Beispiel Potenzfunktion mit 𝒑 = 𝒂
◼ Iterative Formulierung powIt()

◼ Beispiel 𝐚 = 𝟐, 𝐧 = 𝟐 → 𝟐𝟐
1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis
◼ Anstatt 𝒑 = 𝒂𝒏 können wir auch schreiben
1, für 𝑛 = 0 a=2, n=2 2 * powRe(2, 1)
𝑎𝑛 = ቊ
𝑎 ∙ 𝑎𝑛−1 , sonst a=2, n=1 2 * powRe(2, 0)
➢ Somit haben wir einen rekursiven Ansatz a=2, n=0 1 1
a=2, n=1 2*1 2
a=2, n=2 2*2 4
Iterative und rekursive Funktionen (Beispiel)
◼ Rekursive Formulierung powRe()
𝒏
◼ Beispiel Potenzfunktion mit 𝒑 = 𝒂
◼ Iterative Formulierung powIt()

◼ Beispiel 𝐚 = 𝟐, 𝐧 = 𝟐 → 𝟐𝟐
1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis
◼ Anstatt 𝒑 = 𝒂𝒏 können wir auch schreiben
1, für 𝑛 = 0 a=2, n=2 2 * powRe(2, 1)
𝑎𝑛 = ቊ
𝑎 ∙ 𝑎𝑛−1 , sonst a=2, n=1 2 * powRe(2, 0)
➢ Somit haben wir einen rekursiven Ansatz a=2, n=0 1 1
a=2, n=1 2*1 2
a=2, n=2 2*2 4
Iterative und rekursive Funktionen (Beispiel)
◼ Rekursive Formulierung powRe()
𝒏
◼ Beispiel Potenzfunktion mit 𝒑 = 𝒂
◼ Iterative Formulierung powIt()

◼ Beispiel 𝐚 = 𝟐, 𝐧 = 𝟐 → 𝟐𝟐
1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis
◼ Anstatt 𝒑 = 𝒂𝒏 können wir auch schreiben
1, für 𝑛 = 0 a=2, n=2 2 * powRe(2, 1)
𝑎𝑛 = ቊ
𝑎 ∙ 𝑎𝑛−1 , sonst a=2, n=1 2 * powRe(2, 0)
➢ Somit haben wir einen rekursiven Ansatz a=2, n=0 1 1
a=2, n=1 2*1 2
a=2, n=2 2*2 4
Iterative und rekursive Funktionen (Beispiel)
◼ Rekursive Formulierung powRe()
𝒏
◼ Beispiel Potenzfunktion mit 𝒑 = 𝒂
◼ Iterative Formulierung powIt()

◼ Beispiel 𝐚 = 𝟐, 𝐧 = 𝟐 → 𝟐𝟐
1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis
◼ Anstatt 𝒑 = 𝒂𝒏 können wir auch schreiben
1, für 𝑛 = 0 a=2, n=2 2 * powRe(2, 1)
𝑎𝑛 = ቊ
𝑎 ∙ 𝑎𝑛−1 , sonst a=2, n=1 2 * powRe(2, 0)
➢ Somit haben wir einen rekursiven Ansatz a=2, n=0 1 1
a=2, n=1 2*1 2
a=2, n=2 2*2 4
Iterative und rekursive Funktionen (Beispiel)
◼ Rekursive Formulierung powRe()
𝒏
◼ Beispiel Potenzfunktion mit 𝒑 = 𝒂
◼ Iterative Formulierung powIt()
Abbruchbedingung

◼ Beispiel 𝐚 = 𝟐, 𝐧 = 𝟐 → 𝟐𝟐
1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis
◼ Anstatt 𝒑 = 𝒂𝒏 können wir auch schreiben
1, für 𝑛 = 0 a=2, n=2 2 * powRe(2, 1)
𝑎𝑛 = ቊ
𝑎 ∙ 𝑎𝑛−1 , sonst a=2, n=1 2 * powRe(2, 0)
➢ Somit haben wir einen rekursiven Ansatz a=2, n=0 1 1
a=2, n=1 2*1 2
a=2, n=2 2*2 4
Iterative und rekursive Funktionen (Beispiel)
◼ Rekursive Formulierung powRe()
𝒏
◼ Beispiel Potenzfunktion mit 𝒑 = 𝒂
◼ Iterative Formulierung powIt()

◼ Beispiel 𝐚 = 𝟐, 𝐧 = 𝟐 → 𝟐𝟐
Sich selbst aufrufend
1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis
◼ Anstatt 𝒑 = 𝒂𝒏 können wir auch schreiben
1, für 𝑛 = 0 a=2, n=2 2 * powRe(2, 1)
𝑎𝑛 = ቊ
𝑎 ∙ 𝑎𝑛−1 , sonst a=2, n=1 2 * powRe(2, 0)
➢ Somit haben wir einen rekursiven Ansatz a=2, n=0 1 1
a=2, n=1 2*1 2
a=2, n=2 2*2 4
Iterative und rekursive Funktionen (Beispiel)
◼ Rekursive Formulierung powRe()
𝒏
◼ Beispiel Potenzfunktion mit 𝒑 = 𝒂
◼ Iterative Formulierung powIt()

◼ Beispiel 𝐚 = 𝟑, 𝐧 = 𝟑 → 𝟑𝟐
1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis
◼ Anstatt 𝒑 = 𝒂𝒏 können wir auch schreiben
1, für 𝑛 = 0 a=3, n=2 3 * powRe(3, 1)
𝑎𝑛 = ቊ
𝑎 ∙ 𝑎𝑛−1 , sonst a=2, n=1 2 * powRe(2, 0)
➢ Somit haben wir einen rekursiven Ansatz a=2, n=0 1 1
a=2, n=1 2*1 2
a=2, n=2 2*2 4
Iterative und rekursive Funktionen (Beispiel)
◼ Rekursive Formulierung powRe()
𝒏
◼ Beispiel Potenzfunktion mit 𝒑 = 𝒂
◼ Iterative Formulierung powIt()

Sich selbst aufrufend

◼ Beispiel 𝐚 = 𝟑, 𝐧 = 𝟑 → 𝟑𝟐
1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis
◼ Anstatt 𝒑 = 𝒂𝒏 können wir auch schreiben
1, für 𝑛 = 0 a=3, n=2 3 * powRe(3, 1)
𝑎𝑛 = ቊ
𝑎 ∙ 𝑎𝑛−1 , sonst a=2, n=1 2 * powRe(2, 0)
➢ Somit haben wir einen rekursiven Ansatz Sich selbst aufrufend
a=2, n=0 1 1
a=2, n=1 2*1 2
a=2, n=2 2*2 4
Iterative und rekursive Funktionen (Beispiel)
◼ Rekursive Formulierung powRe()
𝒏
◼ Beispiel Potenzfunktion mit 𝒑 = 𝒂
◼ Iterative Formulierung powIt()

Sich selbst aufrufend

◼ Beispiel 𝐚 = 𝟑, 𝐧 = 𝟑 → 𝟑𝟐
1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis
◼ Anstatt 𝒑 = 𝒂𝒏 können wir auch schreiben
1, für 𝑛 = 0 a=3, n=2 3 * powRe(3, 1)
𝑎𝑛 = ቊ
𝑎 ∙ 𝑎𝑛−1 , sonst a=2, n=1 2 * powRe(2, 0)
➢ Somit haben wir einen rekursiven Ansatz Sich selbst aufrufend
a=2, n=0 1 1
a=2, n=1 2*1 2
a=2, n=2 2*2 4
Iterative und rekursive Funktionen (Beispiel)
◼ Rekursive Formulierung powRe()
𝒏
◼ Beispiel Potenzfunktion mit 𝒑 = 𝒂
◼ Iterative Formulierung powIt()

◼ Beispiel 𝐚 = 𝟑, 𝐧 = 𝟑 → 𝟑𝟐
1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis
◼ Anstatt 𝒑 = 𝒂𝒏 können wir auch schreiben
1, für 𝑛 = 0 a=3, n=2 3 * powRe(3, 1)
𝑎𝑛 = ቊ
𝑎 ∙ 𝑎𝑛−1 , sonst a=3, n=1 3 * powRe(3, 0)
➢ Somit haben wir einen rekursiven Ansatz a=2, n=0 1 1
a=2, n=1 2*1 2
a=2, n=2 2*2 4
Iterative und rekursive Funktionen (Beispiel)
◼ Rekursive Formulierung powRe()
𝒏
◼ Beispiel Potenzfunktion mit 𝒑 = 𝒂
◼ Iterative Formulierung powIt()
Abbruchbedingung

◼ Beispiel 𝐚 = 𝟑, 𝐧 = 𝟑 → 𝟑𝟐
1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis
◼ Anstatt 𝒑 = 𝒂𝒏 können wir auch schreiben
1, für 𝑛 = 0 a=3, n=2 3 * powRe(3, 1)
𝑎𝑛 = ቊ
𝑎 ∙ 𝑎𝑛−1 , sonst a=3, n=1 3 * powRe(3, 0)
➢ Somit haben wir einen rekursiven Ansatz a=3, n=0 1 1
a=2, n=1 2*1 2
a=2, n=2 2*2 4
Iterative und rekursive Funktionen (Beispiel)
◼ Rekursive Formulierung powRe()
𝒏
◼ Beispiel Potenzfunktion mit 𝒑 = 𝒂
◼ Iterative Formulierung powIt()

◼ Beispiel 𝐚 = 𝟑, 𝐧 = 𝟑 → 𝟑𝟐
1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis
◼ Anstatt 𝒑 = 𝒂𝒏 können wir auch schreiben
1, für 𝑛 = 0 a=3, n=2 3 * powRe(3, 1)
𝑎𝑛 = ቊ
𝑎 ∙ 𝑎𝑛−1 , sonst a=3, n=1 3 * powRe(3, 0)
➢ Somit haben wir einen rekursiven Ansatz a=3, n=0 1 1
a=2, n=1 2*1 2
a=2, n=2 2*2 4
Iterative und rekursive Funktionen (Beispiel)
◼ Rekursive Formulierung powRe()
𝒏
◼ Beispiel Potenzfunktion mit 𝒑 = 𝒂
◼ Iterative Formulierung powIt()

◼ Beispiel 𝐚 = 𝟑, 𝐧 = 𝟑 → 𝟑𝟐
1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis
◼ Anstatt 𝒑 = 𝒂𝒏 können wir auch schreiben
1, für 𝑛 = 0 a=3, n=2 3 * powRe(3, 1)
𝑎𝑛 = ቊ
𝑎 ∙ 𝑎𝑛−1 , sonst a=3, n=1 3 * powRe(3, 0) 3*1
➢ Somit haben wir einen rekursiven Ansatz a=3, n=0 1 1
a=2, n=1 2*1 2
a=2, n=2 2*2 4
Iterative und rekursive Funktionen (Beispiel)
◼ Rekursive Formulierung powRe()
𝒏
◼ Beispiel Potenzfunktion mit 𝒑 = 𝒂
◼ Iterative Formulierung powIt()

◼ Beispiel 𝐚 = 𝟑, 𝐧 = 𝟑 → 𝟑𝟐
1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis
◼ Anstatt 𝒑 = 𝒂𝒏 können wir auch schreiben
1, für 𝑛 = 0 a=3, n=2 3 * powRe(3, 1)
𝑎𝑛 = ቊ
𝑎 ∙ 𝑎𝑛−1 , sonst a=3, n=1 3 * powRe(3, 0) 3*1
➢ Somit haben wir einen rekursiven Ansatz a=3, n=0 1 1
a=2, n=1 2*1 2
a=2, n=2 2*2 4
Iterative und rekursive Funktionen (Beispiel)
◼ Rekursive Formulierung powRe()
𝒏
◼ Beispiel Potenzfunktion mit 𝒑 = 𝒂
◼ Iterative Formulierung powIt()

◼ Beispiel 𝐚 = 𝟑, 𝐧 = 𝟑 → 𝟑𝟐
1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis
◼ Anstatt 𝒑 = 𝒂𝒏 können wir auch schreiben
1, für 𝑛 = 0 a=3, n=2 3 * powRe(3, 1) 3*3*1
𝑎𝑛 = ቊ
𝑎 ∙ 𝑎𝑛−1 , sonst a=3, n=1 3 * powRe(3, 0) 3*1
➢ Somit haben wir einen rekursiven Ansatz a=3, n=0 1 1
a=2, n=1 2*1 2
a=2, n=2 2*2 4
Iterative und rekursive Funktionen (Beispiel)

◼ Hauptprogramm Potenzfunktion

◼ Ausgabe
Iterative und rekursive Funktionen (Beispiel 2)
◼ Rekursive Formulierung facultyRe()
◼ Beispiel Fakultät faculty(k) mit 𝑘! = ς𝑘𝑛=1 𝑛
◼ Iterative Formulierung facultyIt()

◼ Beispiel 𝒏 = 𝟑
◼ Anstatt 𝑘! = ς𝑘𝑛=1 𝑛 können wir auch 1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis
schreiben
k=3 3 * facultyRe(2)
1, falls 𝑘 = 1
𝑘! = ቊ k=2 2 * facultyRe(1)
𝑘 ∙ 𝑘 − 1 !, ∀𝑘 > 1
k=1 1 1
➢ Somit haben wir eine rekursive Vorschrift
k=2 2*1 2
k=3 3*2*1 6
Iterative und rekursive Funktionen (Beispiel 2)
◼ Rekursive Formulierung facultyRe()
◼ Beispiel Fakultät faculty(k) mit 𝑘! = ς𝑘𝑛=1 𝑛
◼ Iterative Formulierung facultyIt()

◼ Beispiel 𝒏 = 𝟑
◼ Anstatt 𝑘! = ς𝑘𝑛=1 𝑛 können wir auch 1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis
schreiben
k=3 3 * facultyRe(2)
1, falls 𝑘 = 1
𝑘! = ቊ k=2 2 * facultyRe(1)
𝑘 ∙ 𝑘 − 1 !, ∀𝑘 > 1
k=1 1 1
➢ Somit haben wir eine rekursive Vorschrift
k=2 2*1 2
k=3 3*2*1 6
Iterative und rekursive Funktionen (Beispiel 2)
◼ Rekursive Formulierung facultyRe()
◼ Beispiel Fakultät faculty(k) mit 𝑘! = ς𝑘𝑛=1 𝑛
◼ Iterative Formulierung facultyIt()

◼ Beispiel 𝒏 = 𝟑
◼ Anstatt 𝑘! = ς𝑘𝑛=1 𝑛 können wir auch 1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis
schreiben
k=3 3 * facultyRe(2)
1, falls 𝑘 = 1
𝑘! = ቊ k=2 2 * facultyRe(1)
𝑘 ∙ 𝑘 − 1 !, ∀𝑘 > 1
k=1 1 1
➢ Somit haben wir eine rekursive Vorschrift
k=2 2*1 2
k=3 3*2*1 6
Iterative und rekursive Funktionen (Beispiel 2)
◼ Rekursive Formulierung facultyRe()
◼ Beispiel Fakultät faculty(k) mit 𝑘! = ς𝑘𝑛=1 𝑛
◼ Iterative Formulierung facultyIt()

Übungsaufgabe…

◼ Beispiel 𝒏 = 𝟑
◼ Anstatt 𝑘! = ς𝑘𝑛=1 𝑛 können wir auch 1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis
schreiben
k=3 3 * facultyRe(2)
1, falls 𝑘 = 1
𝑘! = ቊ k=2 2 * facultyRe(1)
𝑘 ∙ 𝑘 − 1 !, ∀𝑘 > 1
k=1 1 1
➢ Somit haben wir eine rekursive Vorschrift
k=2 2*1 2
k=3 3*2*1 6
Checkliste: was muss bei der Rekursion gegeben sein?

(1) Klarheit: mit welchen Argumenten wird die Funktion ◼ Beispiel Bildschirm-Ausgabe
aufgerufen?

◼ cout << "Die Zahl ist: " << i << endl;

(2) Abbruchbedingung: eine Rekursion muss sicher
zum Halten kommen. Dies wird meist über eine
Bedingung der Funktionsargumente gelöst. ◼ printf("Zahl: %03d\n", i);

(3) Arbeitslast (engl. Workload): Was macht oder

berechnet die Funktion? Werden diese Resultate auf ◼ Beispiel Zurückgabe als Funktionsresultat:
dem Bildschirm ausgeben oder als Funktionsresultat 1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis
zurückgegeben?
k=3 ◼ summe = i + Funktion(i
3 * facultyRe(2)
-1);
k=2 2 * facultyRe(1)
(4) Rekursion selbst: Ein Funktionsaufruf mit ◼ return summe;
k=1 1 1
mindestens einem geänderten Argument muss
gegeben sein! k=2 2*1 2
k=3 ◼ return Funktion (i
3 * 2/* 2);
1 6
Mehr Übungen: Rekursion (1)

◼ Welche Ausgabe produziert ◼ Die berühmte Mathematikerin ◼ Schreiben Sie einen Countdown,
diese Funktion für Dr. G. Auss hat folgende der von 10 abwärts zählt und die
Eingabewerte > 0 ? [1] Funktion zur Berechnung einer Zahlen jeweils ausgibt.
Summe vorgeschlagen. Was hat An Stelle von 0 soll allerdings
Dr. Auss übersehen? "Go" ausgegeben werden.

1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis

k=3 3 * facultyRe(2)
k=2 2 * facultyRe(1)
k=1 1 1
k=2 2*1 2
k=3 3*2*1 6
Mehr Übungen: Rekursion (1)

◼ Welche Ausgabe produziert ◼ Die berühmte Mathematikerin ◼ Schreiben Sie einen Countdown,
diese Funktion für Dr. G. Auss hat folgende der von 10 abwärts zählt und die
Eingabewerte > 0 ? [1] Funktion zur Berechnung einer Zahlen jeweils ausgibt.
Summe vorgeschlagen. Was hat An Stelle von 0 soll allerdings
Dr. Auss übersehen? "Go" ausgegeben werden.

1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis

k=3 3 * facultyRe(2)
k=2 2 * facultyRe(1)
k=1 1 1
k=2 2*1 2
k=3 3*2*1 6
Mehr Übungen: Rekursion (1)

Lösung:
◼ Welche Ausgabe produziert
diese Funktion für ◼ Die Funktion spring immer zwischen positiven und negativen
Eingabewerte > 0 ? [1] Zahlen hin- und her und halbiert diese im Betrag dabei jeweils,
so dass sie sicher bei der Division

1 𝑜𝑑𝑒𝑟 − 1
=0
2

zum Halten kommt.

1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis

k=3 3 * facultyRe(2)
k=2 2 * facultyRe(1)
k=1 1 1
k=2 2*1 2
k=3 3*2*1 6
Mehr Übungen: Rekursion (1)

◼ Welche Ausgabe produziert ◼ Die berühmte Mathematikerin ◼ Schreiben Sie einen Countdown,
diese Funktion für Dr. G. Auss hat folgende der von 10 abwärts zählt und die
Eingabewerte > 0 ? [1] Funktion zur Berechnung einer Zahlen jeweils ausgibt.
Summe vorgeschlagen. Was hat An Stelle von 0 soll allerdings
Dr. Auss übersehen? "Go" ausgegeben werden.

1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis

k=3 3 * facultyRe(2)
k=2 2 * facultyRe(1)
k=1 1 1
k=2 2*1 2
k=3 3*2*1 6
Mehr Übungen: Rekursion (1)

◼ Welche Ausgabe produziert ◼ Die berühmte Mathematikerin ◼ Schreiben Sie einen Countdown,
diese Funktion für Dr. G. Auss hat folgende der von 10 abwärts zählt und die
Eingabewerte > 0 ? [1] Funktion zur Berechnung einer Zahlen jeweils ausgibt.
Summe vorgeschlagen. Was hat An Stelle von 0 soll allerdings
Dr. Auss übersehen? "Go" ausgegeben werden.

1. Aufruf 2. Aufruf 3. Aufruf Berechnung Ergebnis

Lösung k=3 3 * facultyRe(2)

k=2 2 * facultyRe(1)
◼ Die Funktion hat keine Abbruchbedingung
k=1
und kommt daher nicht zum Halten! 1 1
k=2 2*1 2
k=3 3*2*1 6
Mehr Übungen: Rekursion (1)

◼ Welche Ausgabe produziert ◼ Die berühmte Mathematikerin ◼ Schreiben Sie einen Countdown,
diese Funktion für Dr. G. Auss hat folgende der von 10 abwärts zählt und die
Eingabewerte > 0 ? [1] Funktion zur Berechnung einer Zahlen jeweils ausgibt.
Summe vorgeschlagen. Was hat An Stelle von 0 soll allerdings
Dr. Auss übersehen? "Go" ausgegeben werden.
Die Türme von Hanoi

Paradebeispiel für eine Rekursionslösung:

• Rekursion leicht zu entwickeln
• Nicht-rekursive Lösung ist komplizierte und schwierig zu finden
Die Türme von Hanoi
Die Geschichte: Buddhistische Mönche des Brahma-Tempels haben die Aufgabe, 64 Scheiben aus Gold, die ein Loch in der
Mitte haben, von Stab A nach Stab B zu bringen. Stab C kann als Zwischenablage dienen.

Die Mönche müssen zwei Regeln beachten:

1. Es darf nur eine Scheibe zurzeit bewegt werden.
2. Nie darf eine größere auf einer kleineren Scheibe zu liegen kommen.
Die Legende sagt, dass das Ende der Welt kommt, wenn die Mönche ihre Aufgabe

Die Legende* sagt, dass das Ende der Welt kommt, wenn die Mönche ihre Aufgabe beendet haben.

(*) Die Wahrheit über den Ursprung der „Legende“ finden Sie hier:
[Link]
[Link]
Die Türme von Hanoi (online spielen)

[Link]
Rekursive Lösung: Türme von Hanoi
Start: Ziel

A B C
Rekursive Lösung: Türme von Hanoi
Start: Ziel

A B C

Wenn wir wüssten, wie man die oberen 7 bis auf die letzte Schreibe auf Stab C bringen könnte,
wäre das Problem schon einfacher…
Rekursive Lösung: Türme von Hanoi
Start: Ziel

A B C

Wenn wir wüssten, wie man die oberen 7 bis auf die letzte Schreibe auf Stab C bringen könnte,
wäre das Problem schon einfacher… dann nur Scheibe 8 nach B …..
Rekursive Lösung: Türme von Hanoi
Start: Ziel

A B C

Wenn wir wüssten, wie man die oberen 7 bis auf die letzte Schreibe auf Stab C bringen könnte,
wäre das Problem schon einfacher… dann nur Scheibe 8 nach B .. dann 7 Scheiben nach B.
Rekursive Lösung: Türme von Hanoi
Start: Ziel

A B C

Start:
8 Scheiben nach B

Wenn wir wüssten, wie man die oberen 7 bis auf die letzte Schreibe auf Stab C bringen könnte,
wäre das Problem schon einfacher… dann nur Scheibe 8 nach B .. dann 7 Scheiben nach B.
Rekursive Lösung: Türme von Hanoi
Aufgabe: 8 Scheiben von A nach B:
− 7 bis auf die letzte Schreibe von Stab A auf Stab C; 8te von Stab A nach Stab B; 7 Scheiben von Stab C nach B.
− 6 bis auf die letzte Schreibe von Stab C auf Stab A; 8te von Stab A nach Stab B; 7 Scheiben von Stab C nach A

A 1 B C

2 3
Rekursive Lösung: Türme von Hanoi
Aufgabe: 8 Scheiben von A nach B:
− 7 bis auf die letzte Schreibe von Stab A auf Stab C; 8te von Stab A nach Stab B; 7 Scheiben von Stab C nach B.
− 6 bis auf die letzte Schreibe von Stab C auf Stab A; 8te von Stab A nach Stab B; 7 Scheiben von Stab C nach A

A B C

? ?
?
Rekursive Lösung: Türme von Hanoi
Aufgabe: 8 Scheiben von A nach B:
− 7 bis auf die letzte Schreibe von Stab A auf Stab C; 8te von Stab A nach Stab B; 7 Scheiben von Stab C nach B.
− 6 bis auf die letzte Schreibe von Stab C auf Stab A; 7te von Stab C nach Stab B; 6 Scheiben von Stab A nach B

A B C

3 1
2
Rekursive Lösung: Türme von Hanoi
Aufgabe: 8 Scheiben von A nach B:
− 7 bis auf die letzte Schreibe von Stab A auf Stab C; 8te von Stab A nach Stab B; 7 Scheiben von Stab C nach B.
− 6 bis auf die letzte Schreibe von Stab C auf Stab A; 7te von Stab C nach Stab B; 6 Scheiben von Stab A nach B

A B C

? ?
?
Rekursive Lösung: Türme von Hanoi
Aufgabe: 8 Scheiben von A nach B:
− 7 bis auf die letzte Schreibe von Stab A auf Stab C; 8te von Stab A nach Stab B; 7 Scheiben von Stab C nach B.
− 6 bis auf die letzte Schreibe von Stab C auf Stab A; 7te von Stab C nach Stab B; 6 Scheiben von Stab A nach B
− 5 bis auf die letzte Schreibe von Stab A auf Stab C; 6te von Stab A nach Stab B; 5 Scheiben von Stab C nach B

A 1 B C

2 3
Rekursive Lösung: Türme von Hanoi
Aufgabe: 8 Scheiben von A nach B:
− 7 bis auf die letzte Schreibe von Stab A auf Stab C; 8te von Stab A nach Stab B; 7 Scheiben von Stab C nach B.
− 6 bis auf die letzte Schreibe von Stab C auf Stab A; 7te von Stab C nach Stab B; 6 Scheiben von Stab A nach B
− 5 bis auf die letzte Schreibe von Stab A auf Stab C; 6te von Stab A nach Stab B; 5 Scheiben von Stab C nach B
usw…

Abbruchbedingung: Nur noch eine Scheibe muss bewegt werden, das geht nach Regeln.
 Rekursive Lösung: Türme von Hanoi
Aufgabe: 8 Scheiben von A nach B:
− 7 bis auf die letzte Schreibe von Stab A auf Stab C; 8te von Stab A nach Stab B; 7 Scheiben von Stab C nach B.
− 6 bis auf die letzte Schreibe von Stab C auf Stab A; 7te von Stab C nach Stab B; 6 Scheiben von Stab A nach B
− 5 bis auf die letzte Schreibe von Stab A auf Stab C; 6te von Stab A nach Stab B; 5 Scheiben von Stab C nach B
usw…

1Abbruchbedingung: Nur noch eine Scheibe muss bewegt werden, das geht nach Regeln.

void Bewege(char StartStapel, char ZielStapel, char ArbeitsStapel, int wieviele) {

if (wieviele == 1) { 1
cout << "Bewege Scheibe von "<< StartStapel << " nach " << ZielStapel << endl;
return;
}
Bewege(StartStapel, ArbeitsStapel, ZielStapel, wieviele-1);
Bewege(StartStapel, ZielStapel, ArbeitsStapel, 1);
Bewege(ArbeitsStapel, ZielStapel, StartStapel, wieviele-1);
}
 Rekursive Lösung: Türme von Hanoi
Aufgabe: 8 Scheiben von A nach B: 2
− 7 bis auf die letzte Schreibe von Stab A auf Stab C; 8te von Stab A nach Stab B; 7 Scheiben von Stab C nach B.
− 6 bis auf die letzte Schreibe von Stab C auf Stab A; 7te von Stab C nach Stab B; 6 Scheiben von Stab A nach B
− 5 bis auf die letzte Schreibe von Stab A auf Stab C; 6te von Stab A nach Stab B; 5 Scheiben von Stab C nach B
usw…

1Abbruchbedingung: Nur noch eine Scheibe muss bewegt werden, das geht nach Regeln.

void Bewege(char StartStapel, char ZielStapel, char ArbeitsStapel, int wieviele) {

if (wieviele == 1) { 1
cout << "Bewege Scheibe von "<< StartStapel << " nach " << ZielStapel << endl;
return;
}
Bewege(StartStapel, ArbeitsStapel, ZielStapel, wieviele-1); 2
Bewege(StartStapel, ZielStapel, ArbeitsStapel, 1);
Bewege(ArbeitsStapel, ZielStapel, StartStapel, wieviele-1);
}
 Rekursive Lösung: Türme von Hanoi
Aufgabe: 8 Scheiben von A nach B: 2 3
− 7 bis auf die letzte Schreibe von Stab A auf Stab C; 8te von Stab A nach Stab B; 7 Scheiben von Stab C nach B.
− 6 bis auf die letzte Schreibe von Stab C auf Stab A; 7te von Stab C nach Stab B; 6 Scheiben von Stab A nach B
− 5 bis auf die letzte Schreibe von Stab A auf Stab C; 6te von Stab A nach Stab B; 5 Scheiben von Stab C nach B
usw…

1Abbruchbedingung: Nur noch eine Scheibe muss bewegt werden, das geht nach Regeln.

void Bewege(char StartStapel, char ZielStapel, char ArbeitsStapel, int wieviele) {

if (wieviele == 1) { 1
cout << "Bewege Scheibe von "<< StartStapel << " nach " << ZielStapel << endl;
return;
}
Bewege(StartStapel, ArbeitsStapel, ZielStapel, wieviele-1); 2
Bewege(StartStapel, ZielStapel, ArbeitsStapel, 1);
Bewege(ArbeitsStapel, ZielStapel, StartStapel, wieviele-1); 3
}
 Rekursive Lösung: Türme von Hanoi
Aufgabe: 8 Scheiben von A nach B: 2 3 4
− 7 bis auf die letzte Schreibe von Stab A auf Stab C; 8te von Stab A nach Stab B; 7 Scheiben von Stab C nach B.
− 6 bis auf die letzte Schreibe von Stab C auf Stab A; 7te von Stab C nach Stab B; 6 Scheiben von Stab A nach B
− 5 bis auf die letzte Schreibe von Stab A auf Stab C; 6te von Stab A nach Stab B; 5 Scheiben von Stab C nach B
usw…

1Abbruchbedingung: Nur noch eine Scheibe muss bewegt werden, das geht nach Regeln.

void Bewege(char StartStapel, char ZielStapel, char ArbeitsStapel, int wieviele) {

if (wieviele == 1) { 1
cout << "Bewege Scheibe von "<< StartStapel << " nach " << ZielStapel << endl;
return;
}
Bewege(StartStapel, ArbeitsStapel, ZielStapel, wieviele-1); 2
Bewege(StartStapel, ZielStapel, ArbeitsStapel, 1);
Bewege(ArbeitsStapel, ZielStapel, StartStapel, wieviele-1); 3
}
4
 Rekursive Lösung: Türme von Hanoi
Aufgabe: 8 Scheiben von A nach B: 2 3 4
− 7 bis auf die letzte Schreibe von Stab A auf Stab C; 8te von Stab A nach Stab B; 7 Scheiben von Stab C nach B.
− 6 bis auf die letzte Schreibe von Stab C auf Stab A; 7te von Stab C nach Stab B; 6 Scheiben von Stab A nach B
− 5 bis auf die letzte Schreibe von Stab A auf Stab C; 6te von Stab A nach Stab B; 5 Scheiben von Stab C nach B
usw…

1Abbruchbedingung: Nur noch eine Scheibe muss bewegt werden, das geht nach Regeln.
5 Information über den jeweiligen
Arbeitsstapel
void Bewege(char StartStapel, char ZielStapel, char ArbeitsStapel, int wieviele) {
if (wieviele == 1) { 1
cout << "Bewege Scheibe von "<< StartStapel << " nach " << ZielStapel << endl;
return;
}
Bewege(StartStapel, ArbeitsStapel, ZielStapel, wieviele-1); 2
Bewege(StartStapel, ZielStapel, ArbeitsStapel, 1);
Bewege(ArbeitsStapel, ZielStapel, StartStapel, wieviele-1); 3
}
4
Rekursive Lösung: Türme von Hanoi

Lösung für 3 Scheiben:

Die Gesamtzahl der Bewegungen für k Scheiben

ist gegeben durch 𝑁 = 2𝑘 − 1.

Somit bei 64 Goldscheiben bräuchten die

Mönche (1s pro Zug) ungefähr 5,86 ⋅ 1011 Jahre.
Das entspricht etwa dem 50-fachen Alter unseres
Universums.
Rekursive Lösung: Türme von Hanoi

Lösung für 3 Scheiben:

Die Gesamtzahl der Bewegungen für k Scheiben

ist gegeben durch 𝑁 = 2𝑘 − 1.

Somit bei 64 Goldscheiben bräuchten die

Mönche (1s pro Zug) ungefähr 5,86 ⋅ 1011 Jahre.
Das entspricht etwa dem 50-fachen Alter unseres
Universums.
 Let‘s Code: Kochkurve (Scratch)

Python code siehe: [Link]

 Let‘s Code: Kochkurve (Scratch)

Python code siehe: [Link]

[Link]