Algorithmen und Datenstrukturen

Rekursion

Prof. Justus Piater, Ph.D.

9. März 2025

Dieser Kurs folgt in weiten Teilen dem sehr empfehlenswerten Lehrbuch

Data Structures and Algorithms in Java [Goodrich u. a. 2014].

Inhaltsverzeichnis

1 Fakultät 2

2 Binärsuche 6

3 Verzeichnisbaum 9

4 Kombinationen 19

5 Eigenschaften 21

6 Zusammenfassung 26

Viele Probleme lassen sich als Erweiterung einer kleineren Version desselben Problems
Einführung

formulieren. Eine solche Formulierung nennt man rekursiv. Dieses Prinzip im Allgemei-
nen und die rekursive Lösung von Problemen im Speziellen bezeichnet man als Rekur-
sion.
Vielleicht kennen Sie das Problem der Türme von Hanoi? Ich muss diesen Turm auf das
mittlere Feld verschieben. Allerdings darf ich immer nur einen Stein zur Zeit bewegen,
und es darf niemals ein größerer Stein auf einem kleineren liegen. Wie gehe ich hier vor?
Wie geht der Türme-von-Hanoi-Algorithmus?
Ganz einfach: Ich wende den Türme-von-Hanoi-Algorithmus rekursiv an, um die obersten
drei Steine auf das rechte Feld zu verschieben. Dann kann ich den größten Stein nehmen
und direkt auf das mittlere Feld legen. Anschließend wende ich wiederum den Türme-
von-Hanoi-Algorithmus an, um den rechten Turm auf den mittleren Stein zu stellen.
Aber wie wende ich den Türme-von-Hanoi-Algorithmus auf die obersten drei Steine an?
Ich kenne diesen Algorithmus ja gar nicht! Aber kein Problem: Ich wende den Türme-
von-Hanoi-Algorithmus rekursiv an, um die obersten zwei Steine auf das mittlere Feld
zu verlegen, und dann kann ich den dritten Stein auf das rechte Feld verschieben und
mittels des Türme-von-Hanoi-Algorithmus den mittleren Zweier-Turm auf den rechten
Stein stellen.
Aber wie verwende ich den Türme-von-Hanoi-Algorithmus, umd die beiden obersten
Steine auf das mittlere Feld zu verlegen? Ganz einfach: Ich nehme den obersten Stein
und verlege ihn auf das rechte Feld. Dann kann ich den nun obersten Stein von links

1
 auf die Mitte verlegen und anschließend den kleinsten Stein von rechts auf den mittleren
Turm.
Nachdem ich den größten Stein erfolgreich in die Mitte verlegt habe, wie kann ich den
rechten Turm seinerseits in die Mitte verlegen? Ganz einfach: Ich wende den Türme-von-
Hanoi-Algorithmus rekursiv an, um die beiden obersten Steine nach links zu verlegen.
Dann kann ich den untersten Stein von rechts auf die Mitte verlegen und anschließend
die beiden linken Steine per Türme-von-Hanoi-Algorithmus obenauf setzen.
Die Rekursion besteht also darin, dass der Algorithmus sich selbst aufruft, und zwar auf
einer kleineren Version des Originalproblems. Irgendwann wird das Problem so klein, dass
es trivial lösbar ist, nämlich einen einzelnen Stein auf ein anderes Feld zu verlegen. Dies
ist ein typisches Beispiel für die Eleganz und Einfachheit vieler rekursiver Algorithmen
bei der Lösung augenscheinlich komplexer Probleme.

1 Fakultät

Video 1 beginnt hier.

Fakultät: iterative Version [Slide 1]

𝑛
𝑛! = ∏ 𝑖
𝑖=1

Algorithm factorial(𝑛):
Require: Integer 𝑛 ≥ 0.
Ensure: Return 𝑛!.
𝑓 ←1
for 𝑖 ← 2 to 𝑛 do
𝑓 ← 𝑓𝑖
return 𝑓

Schauen wir uns zunächst eine einfache Funktion in einer nicht-rekursiven Formulierung
Beispiel

an. 𝑛-Fakultät können wir als das Produkt der ganzen Zahlen von 1 bis 𝑛 formulieren.
Diese Definition lässt sich leicht in einen iterativen Algorithmus zur Berechnung von 𝑛-
Fakultät übersetzen: Wir beginnen mit dem Wert 1, und multiplizieren dort alle folgenden
ganzen Zahlen bis einschließlich 𝑛 nacheinander hinein.

2
 Fakultät: rekursive Version [Slide 2]

1 if 𝑛 = 0 Rekursionsanfang
𝑛! = {
𝑛(𝑛 − 1)! otherwise Rekursionsschritt

Beispiel
4! = 4 ⋅ 3! = 4 ⋅ (3 ⋅ 2 ⋅ 1)

Algorithm factorial(𝑛):
Require: integer 𝑛 ≥ 0.
Ensure: Return 𝑛!.
if 𝑛 = 0 then
return 1 // Rekursionsanfang
else
return 𝑛×factorial(𝑛 − 1) // Rekursionsschritt

Betrachten wir nun diese rekursive Definition der Fakultät. Hier definieren wir 𝑛-
Beispiel

Fakultät als 𝑛 mal 𝑛 − 1-Fakultät. Die Rekursion dieser Definition besteht darin, dass
die Fakultät durch die Fakultät definiert wird.
Das funktioniert natürlich nur, wenn die Rekursion irgendwo endet. Dies ist hier für
𝑛 = 0 der Fall: 0-Fakultät wird gesondert behandelt und ist als der Wert 1 definiert
anstatt rekursiv als 0 · (0 − 1)-Fakultät.
Dies ist der sogenannte Rekursionsanfang. Den anderen Fall 𝑛(𝑛 − 1)! bezeichnet man
als den Rekursionsschritt. Jede Rekursion beinhaltet mindestens einen Rekursionsan-
fang und mindestens einen Rekursionsschritt.
Unsere rekursive Definition der Fakultät lässt sich wiederum unmittelbar in einen rekur-
siven Algorithmus zur Berechnung der Fakultät von 𝑛 übersetzen. Die Rekursion dieses
Algorithmus besteht darin, dass er sich selbst aufruft.

Aufrufbaum: factorial(4) [Slide 3]

Algorithm factorial(𝑛): Aufruf Argument n

Stack (in RAM)
if 𝑛 = 0 then
return 1
else factorial(4) 4
return 𝑛×factorial(𝑛 − 1)
factorial(3) 3

factorial(2) 2

factorial(1) 1

factorial(0) 0

Wird factorial(4) aufgerufen, ist 𝑛 = 4 und nicht 0. Daher ruft sich die Funktion
Beispiel

factorial im else-Zweig selbst auf, mit dem Argument 𝑛 − 1 = 3. Wir haben nun zwei
aktive Aufrufe dieser Funktion, von denen jeder einen eigenen Speicherbereich für sein
Argument besitzt.
Im Speicherbereich des ersten Aufrufs von factorial liegt die Variable 𝑛 mit dem
Wert 4, und im Speicherbereich des zweiten Aufrufs von factorial liegt die Varia-
ble 𝑛 mit dem Wert 3. Der erste Aufruf wartet nun, bis der zweite Aufruf endet und

3
 seinen Rückgabewert liefert, um diesen mit seinem Wert von 𝑛 zu multiplizieren und
seinerseits an seinen Aufrufer zurückzugeben.
Der zweite Aufruf von factorial verhält sich genauso wie der erste. Er ruft seinerseits
rekursiv factorial auf, mit dem Argument 𝑛 − 1 = 2. Diese rekursiven Aufrufe setzen
sich fort, bis schließlich beim 5. Aufruf 𝑛 = 0 und damit der Rekursionsanfang erreicht
ist.

Aufrufbaum: factorial(4) [Slide 4]

Algorithm factorial(𝑛): Aufruf Argument n

Stack (in RAM)
if 𝑛 = 0 then
return 1
else factorial(4) 4
return 𝑛×factorial(𝑛 − 1)
factorial(3) 3

factorial(2) 2

factorial(1) 1

factorial(0) 0 1

Spätestens hier wird deutlich, dass die Bezeichnung Rekursionsanfang vielleicht

nicht die glücklichste ist: Er bildet das Ende der Berechnung und nicht den Anfang.
Der Begriff Rekursionsanfang soll ausdrücken, dass er die Basis bildet, auf der die
Rekursion ruht.
An dieser Stelle liefert die Funktion unmittelbar den Wert 1 zurück.
Beispiel

Aufrufbaum: factorial(4) [Slide 5]

Algorithm factorial(𝑛): Aufruf Argument n Rückgabewert

Stack (in RAM) Register
if 𝑛 = 0 then
return 1
else factorial(4) 4 × 24
return 𝑛×factorial(𝑛 − 1)
factorial(3) 3 × 6

factorial(2) 2 × 2

factorial(1) 1 × 1

factorial(0) 0 1

Dieser Rückgabewert wird nun vom 4. Aufruf, der bis jetzt darauf gewartet hat, mit
Beispiel

seinem Wert von 𝑛 multipliziert, nämlich 1. Dann wird das Ergebnis an seinen Aufrufer
zurückgeliefert, den 3. Aufruf.
Auf diese Weise kehren auch der 3., 2. und schließlich der 1. Aufruf zurück, der uns das
Endergebnis von factorial(4) liefert, nämlich 24.

4
 Aufrufbaum und asymptotische Laufzeit [Slide 6]

Aufrufbaum: Aufgerufene Funktionen sind die Kindknoten

der aufrufenden Funktion.
Algorithm factorial(𝑛): factorial(4)
if 𝑛 = 0 then
return 1
else factorial(3)
return 𝑛×factorial(𝑛 − 1)

Asymptotische Laufzeit von factorial(): 𝑂 (𝑛), da factorial(2)

genau 𝑛 rekursive Aufrufe stattfinden und die Laufzeiten aller
anderen Anweisungen konstant sind.
factorial(1)

factorial(0)
Für rekursive Aufrufe liefert uns unser voriges Kapitel zur asymptotischen Laufzeit-
analyse keine Hilfsmittel. Für factorial(), wie häufig, gibt uns der Aufrufbaum
entscheidende Hinweise auf das Laufzeitverhalten.
Ein breit einsetzbares Werkzeug für die asymptotische Laufzeitanalyse rekursiver
Algorithmen ist das sogenannte Master-Theorem, das jedoch über den Umfang
dieses Kurses hinausgeht.

Die Abfolge der Funktionsaufrufe eines Algorithmus oder Programms bilden eine Baum-
Erklärung

struktur: Aufgerufene Funktionen bilden die Kindknoten der aufrufenden Funktion.

Insbesondere bei rekursiven Algorithmen stellt der Aufrufbaum ein wichtiges Hilfsmittel
zur Analyse des Laufzeitverhaltens dar. Bei unserem factorial-Algorithmus ruft sich die
factorial-Funktion genau einmal rekursiv auf. Der Aufrufbaum bildet also eine lineare
Liste.
Wie lang ist diese Liste? Wir sehen im Algorithmus, dass sich der Wert von 𝑛 bei jedem
rekursiven Aufruf um 1 vermindert. Da 𝑛 = 0 den Rekursionsanfang bildet, finden also
genau 𝑛 rekursive Aufrufe statt, und die Gesamtzahl der Aufrufe inklusive des ersten ist
genau 𝑛 + 1, also Θ(𝑛).
Da alle anderen Anweisungen des Algorithmus 𝑂(1) sind, also in von 𝑛 unabhängiger
Zeit ablaufen, ist die Gesamtlaufzeit von factorial(n) folglich Θ(𝑛).

5
 2 Binärsuche

Video 2 beginnt hier.

Suche in einer sortierten Sequenz [Slide 7]

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

3 5 6 7 9 10 11 13 15 18 20 23 26 29 31 34

• Ist die Sequenz sortiert und indizierbar, dann kann Binärsuche (bisection
search) angewendet werden.
Ein besserer Begriff wäre Halbierungssuche, denn es handelt sich um Suche
mittels des (als solches bekannten) Halbierungsverfahrens. Der Begriff Hal-
bierungssuche ist allerdings leider nicht gebräuchlich.
Andernfalls muss man i.d.R. auf sequenzielle Suche zurückgreifen.

Binärsuche: Rekursive Suche in einer Hälfte der Sequenz.

Ein typisches Beispiel für die Anwendung von Rekursion ist die Suche nach einem be-
Beispiel

stimmten Element in einer sortierten Sequenz. Die Sortierung der Sequenz können wir
dahingehend nutzen, dasss wir einen Großteil der Elemente bei der Suche überhaupt
nicht betrachten müssen und trotzdem garantiert das gesuchte Element finden bzw. die
Abwesenheit dieses Elements feststellen können. Dies setzt voraus, dass wir auf jedes
Element der Sequenz in konstanter Zeit per Index zugreifen können.

Binärsuche: Beispiel [Slide 8]

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

3 5 6 7 9 10 11 13 15 18 20 23 26 29 31 34

low mid high

3 5 6 7 9 10 11 13 15 18 20 23 26 29 31 34

low mid high

3 5 6 7 9 10 11 13 15 18 20 23 26 29 31 34

low mid high

3 5 6 7 9 10 11 13 15 18 20 23 26 29 31 34

low = mid = high

Die Idee ist ganz einfach: Wir vergleichen das gesuchte Element mit dem Element in der
Beispiel

Mitte der Sequenz. Sind beide identisch, dann haben wir es gefunden. Ist das gesuchte
Element kleiner, suchen wir es rekursiv in der linken Hälfte der Sequenz; ist es größer,
dann suchen wir es rekursiv in der rechten Hälfte.
Falls das gesuchte Element in der Sequenz vorhanden ist, werden wir es auf diese Weise
garantiert finden. Falls das Element nicht vorhanden ist, stellen wir dies fest, wenn die
durchsuchte Teilsequenz leer ist.

6
 Dieser Algorithmus ist im Deutschen als Binärsuche bekannt. Der englische Begriff bi-
section search ist viel treffender, denn er beschreibt in einem Wort, wie der Algorithmus
funktioniert: In jedem Schritt zerschneidet er die Sequenz in zwei Hälften. Das aus dem
Lateinischen stammende Verb to bisect bedeutet wörtlich, etwas in zwei Teile zu schnei-
den. Danach sucht der Algorithmus rekursiv in einer der beiden Hälften weiter.

Binärsuche [Slide 9]

Algorithm bisectionSearch(𝑆, 𝑘, 𝑙, ℎ):

Require: An ordered vector 𝑆 storing at least ℎ + 1 entries,
key 𝑘 sought, and indices 𝑙 (low) and ℎ (high).
Ensure: Return true iff 𝑘 = 𝑆[𝑖] exists for some 𝑙 ≤ 𝑖 ≤ ℎ.
if 𝑙 > ℎ then
return false
𝑚 ← ⌊(𝑙 + ℎ)/2⌋
𝑒 ← 𝑆[𝑚]
if 𝑘 = 𝑒 then
return true
else if 𝑘 < 𝑒 then
return bisectionSearch(𝑆, 𝑘, 𝑙, 𝑚 − 1)
else
return bisectionSearch(𝑆, 𝑘, 𝑚 + 1, ℎ)

Ist unserer Algorithmus bisectionSearch korrekt? Das heißt, findet er garantiert das
Erklärung

gesuchte Element, falls es existiert, und stellt er garantiert seine Abwesenheit fest, falls
es nicht existiert?
Zunächst stellen wir fest, dass der Algorithmus in endlicher Zeit terminiert. 𝑙, ℎ und
𝑚 sind ganzzahlige Indizes. 𝑚 liegt abgerundet in der Mitte zwischen 𝑙 und ℎ. Beide
rekursiven Aufrufe stellen sicher, dass die durchsuchte Teilsequenz echt kürzer wird.
Damit ist sie irgendwann leer, was durch den Rekursionsanfang aufgefangen wird.
Wegen der Sortierung muss sich das gesuchte Element immer in der durchsuchten Teil-
sequenz befinden, falls es existiert. Die einzige Möglichkeit, es zu übersehen, wäre, dass es
nicht getestet wird und sich beim nächsten rekursiven Aufruf außerhalb der neuen Teil-
sequenz befindet. Das ist jedoch ausgeschlossen: Das Element 𝑚 wird mit dem gesuchten
verglichen, und das Element daneben gehört zur anschließend durchsuchten Teilsequenz.
Somit haben wir die Korrektheit des bisectionSearch-Algorithmus nachgewiesen.

7
 Binärsuche: Laufzeitanalyse [Slide 10]

Algorithm bisectionSearch(𝑆, 𝑘, 𝑙, ℎ):

if 𝑙 > ℎ then • Alle Anweisungen sind 𝑂(1), bis
return false auf die rekursiven Aufrufe. Die
𝑚 ← ⌊(𝑙 + ℎ)/2⌋ Laufzeit ist also linear in der
𝑒 ← 𝑆[𝑚] Anzahl der rekursiven Aufrufe.
if 𝑘 = 𝑒 then
• Bei jedem rekursiven Aufruf wird
return true
die Anzahl der verbleibenden
else if 𝑘 < 𝑒 then
Kandidaten halbiert. Nach 𝑖
return bisectionSearch
Aufrufen verbleiben also noch
(𝑆, 𝑘, 𝑙, 𝑚 − 1)
maximal 𝑛/2𝑖 Kandidaten.
else
return bisectionSearch • Die Anzahl der rekursiven Aufrufe
(𝑆, 𝑘, 𝑚 + 1, ℎ) ist also maximal gleich der
kleinsten ganzen Zahl 𝑚 mit
𝑛/2𝑚 < 1, also log 𝑛 < 𝑚, also
𝑚 = ⌊log 𝑛⌋ + 1.
Sobald kein Kandidat mehr ver-
bleibt, ist 𝑛/2𝑚 < 1, und die Re-
kursion endet, d.h., 𝑚 wird nicht
weiter erhöht.

Die Laufzeit von bisectionSearch() ist

also 𝑂(log 𝑛).
Analysieren wir nun das asymptotische Laufzeitverhalten unseres bisectionSearch-
Erklärung

Algorithmus.
Alle Anweisungen laufen in konstanter Zeit, bis auf die rekursiven Aufrufe. Die Laufzeit
ist also linear in der Anzahl der rekursiven Aufrufe.
Um diese zu ermitteln, stellen wir uns wieder die Frage, wie der rekursive Aufrufbaum
aussieht. Die Funktion ruft sich maximal einmal rekursiv auf. Das heißt, unser Aufruf-
baum ist wieder eine lineare Liste, und die Gesamtlaufzeit ist linear in der Länge dieser
Liste, also zur Rekursionstiefe. Was ist also die Rekursionstiefe?
Bei jedem rekursiven Aufruf wird die Anzahl der ursprünglich 𝑛 Kandidaten halbiert.
Nach 𝑖 Aufrufen verbleiben also noch maximal 𝑛/2𝑖 Kandidaten. Sobald diese Zahl 𝑛/2𝑖
unter 1 fällt, ist die Teilsequenz leer, und die Rekursion endet. Dies ist der Fall, wenn
𝑛 < 2𝑖 ist, also log 𝑛 < 𝑖. Die Rekursionstiefe ist also logarithmisch in 𝑛, der Länge der
Eingabesequenz. Damit ist die Laufzeit von bisectionSearch 𝑂(log 𝑛).
Wie eingangs erwähnt ist diese besser-als-lineare Laufzeit erreichbar, weil wir dank der
Sortierung viele Elemente der Sequenz bei der Suche komplett übersprigen können.

8
 3 Verzeichnisbaum

Video 3 beginnt hier.

Verzeichnisbaum [Slide 11]

from pathlib import Path root

afile
def fstree(file, depth): adir
print(' ' ∗ depth ∗ 2 + [Link]) subdir
if file.is_dir(): deepf
for f in [Link](): file
fstree(f, depth + 1) bdir
fileA
fstree(Path('root'), 0) fileB

Anmerkung

Dies ist ein Beispiel für mehrfache Rekursion (multiple recursion): fstree() ruft
sich selbst mehrfach auf.

Sie sind alle mit der hierarchischen Verzeichnisstruktur Ihres Rechners vertraut. Diese
Beispiel

Struktur lässt sich als Baumstruktur darstellen: Die Verzeichnisse und Dateien, die sich
in einem gegebenen Verzeichnis befinden, sind dessen Kinder in der Baumstruktur. Diese
Baumstruktur lässt sich durch eingerückte Zeilen darstellen. Auch dies kennen Sie sicher
von Ihrem Rechner, in grafisch aufgehübschter Form.
Im Beispiel rechts enthält das Verzeichnis root die Datei afile und die Verzeichnisse
adir and bdir, das Verzeichnis adir enthält das Verzeichnis subdir und die Datei file,
usw.
Diese eingerückte Darstellung wurde durch den links gezeigten Python-Code erzeugt.
Falls Ihnen die Programmiersprache Python nicht geläufig ist, macht das überhaupt
nichts. Ignorieren Sie einfach die erste Zeile mit der from-import-Deklaration und lesen
Sie den Rest wie Pseudocode.
Die Funktion fstree, kurz für das englische file system tree, empfängt zwei Argumen-
te, den aktuellen Verzeichniseintrag und die aktuelle Verschachtelungstiefe, und gibt den
Verzeichniseintrag entsprechend eingerückt aus. Dann testet sie mit der Methode is_dir,
ob es sich beim aktuellen Verzeichniseintrag um ein Verzeichnis handelt, englisch direc-
tory. Falls ja, iteriert sie über alle darin enthaltenen Verzeichniseinträge und ruft für
jeden sich selbst rekursiv auf.
Damit handelt es sich um mehrfache Rekursion: Ein gegebener Aufruf von fstree
ruft sich selbst mehrmals rekursiv auf.

9
 Speicherbedarf des Verzeichnisbaums [Slide 12]

from pathlib import Path root (26 Bytes)

afile (15 Bytes)
def fstree(file, depth): adir (20 Bytes)
size = [Link]().st_size subdir (16 Bytes)
print(' ' ∗ depth ∗ 2 + deepf (13 Bytes)
f"{[Link]} ({size} Bytes)") file (9 Bytes)
if file.is_dir(): bdir (20 Bytes)
for f in [Link](): fileA (1 Bytes)
size += fstree(f, depth + 1) fileB (1 Bytes)
return size Total: 121 Bytes
total = fstree(Path('root'), 0)
print(f"Total: {total} Bytes")

Um die Verarbeitung von Rückgabewerten bei einer Mehrfachrekursion zu illustrieren,

Beispiel

haben wir hier unsere Funktion fstree um die Berechnung des Speicherbedarfs der
Dateien und Verzeichnisse erweitert. Für den aktuellen Verzeichniseintrag wird der Spei-
cherbedarf ermittelt, in der Variablen size gespeichert, und zusammen mit dem Ver-
zeichniseintrag ausgegeben. Falls es sich um ein Verzeichnis handelt, wird rekursiv der
Speicherbedarf der darin enthaltenen Verzeichniseinträge ermittelt und auf size aufad-
diert. Damit enthält size die Gesamtgröße des aktuellen Verzeichnisunterbaums, und
wird an den Aufrufer zurückgegeben.

Traversierung des Verzeichnisbaums [Slide 13]

from pathlib import Path Aufruf Arg. u. Variablen Ausgabe

Stack (in RAM)

def fstree(file, depth): fstree(root, 0) root root (26 Bytes)

s = [Link]().st_size 0 afile
26
print("...") adir
fstree(afile, 1) subdir
if file.is_dir():
deepf
for f in [Link](): file
s += fstree(f, depth+1) bdir
return s fileA
fileB

size = fstree(Path('root'), 0)
print(f"Total: {size} Bytes")

Schauen wir uns an, wie fstree den gezeigten Verzeichnisbaum abläuft.
Beispiel

Zu Beginn wird fstree mit dem Wurzelverzeichnis namens root und der Verschach-
telungstiefe 0 aufgerufen. Diese beiden Werte werden im lokalen Speicherbereich dieses
Aufrufs abgelegt, zusammen mit dem Wert 26 der Variablen s, hier verkürzt für size.
Da es sich bei root um ein Verzeichnis handelt, ruft sich fstree anschließend mit dem
ersten Verzeichniseintrag in root auf, nämlich afile, unter Angabe einer um 1 erhöhten
Verschachtelungstiefe.

10
 Traversierung des Verzeichnisbaums [Slide 14]

from pathlib import Path Aufruf Arg. u. Variablen Ausgabe

Stack (in RAM)

def fstree(file, depth): fstree(root, 0) root root (26 Bytes)

s = [Link]().st_size 0 afile (15 Bytes)
26
print("...") += adir
fstree(afile, 1) subdir
if file.is_dir(): afile
1 deepf
for f in [Link](): 15 file
s += fstree(f, depth+1) bdir
return s fileA
fileB

size = fstree(Path('root'), 0)
print(f"Total: {size} Bytes")

fstree(afile, 1) gibt Dateiname und Dateigröße aus. Da es sich nicht um ein Ver-
Beispiel

zeichnis handelt, liefert es nun die Dateigröße von afile zurück.

Traversierung des Verzeichnisbaums [Slide 15]

from pathlib import Path Aufruf Arg. u. Variablen Ausgabe

Stack (in RAM)

def fstree(file, depth): fstree(root, 0) root root (26 Bytes)

s = [Link]().st_size 0 afile (15 Bytes)
41
print("...") adir
subdir
if file.is_dir():
deepf
for f in [Link](): file
s += fstree(f, depth+1) bdir
return s fileA
fileB

size = fstree(Path('root'), 0)
print(f"Total: {size} Bytes")

Der Aufrufer, fstree(root, 0), empfängt diesen Rückgabewert, und addiert ihn zu s.
Beispiel

Damit ist der erste Eintrag im Verzeichnis root abgearbeitet.

11
 Traversierung des Verzeichnisbaums [Slide 16]

from pathlib import Path Aufruf Arg. u. Variablen Ausgabe

Stack (in RAM)

def fstree(file, depth): fstree(root, 0) root root (26 Bytes)

s = [Link]().st_size 0 afile (15 Bytes)
41
print("...") adir
fstree(adir, 1) subdir
if file.is_dir():
deepf
for f in [Link](): file
s += fstree(f, depth+1) bdir
return s fileA
fileB

size = fstree(Path('root'), 0)
print(f"Total: {size} Bytes")

Es folgt der Aufruf für den zweiten Eintrag, adir.

Beispiel

Traversierung des Verzeichnisbaums [Slide 17]

from pathlib import Path Aufruf Arg. u. Variablen Ausgabe

Stack (in RAM)

def fstree(file, depth): fstree(root, 0) root root (26 Bytes)

s = [Link]().st_size 0 afile (15 Bytes)
41
print("...") adir (20 Bytes)
fstree(adir, 1) subdir
if file.is_dir(): adir
1 deepf
for f in [Link](): 20 file
s += fstree(f, depth+1) bdir
fstree(subdir, 2)
return s fileA
fileB

size = fstree(Path('root'), 0)
print(f"Total: {size} Bytes")

Der Aufruf fstree(adir, 1) gibt wiederum den Verzeichnisnamen und seine Größe aus.
Beispiel

Da es sich bei adir um ein Verzeichnis handelt, wird fstree nun rekursiv mit dem ersten
Eintrag dieses Verzeichnisses augerufen.

12
 Traversierung des Verzeichnisbaums [Slide 18]

from pathlib import Path Aufruf Arg. u. Variablen Ausgabe

Stack (in RAM)

def fstree(file, depth): fstree(root, 0) root root (26 Bytes)

s = [Link]().st_size 0 afile (15 Bytes)
41
print("...") adir (20 Bytes)
fstree(adir, 1) subdir (16 B.)
if file.is_dir(): adir
1 deepf
for f in [Link](): 20 file
s += fstree(f, depth+1) bdir
fstree(subdir, 2) subdir
return s 2 fileA
16 fileB

size = fstree(Path('root'), 0) fstree(deepf, 3)

print(f"Total: {size} Bytes")

Dieser Eintrag, subdir, ist ebenfalls ein Verzeichnis. Daher folgt ein weiterer rekursiver
Beispiel

Aufruf, fstree(deepf, 3).

Traversierung des Verzeichnisbaums [Slide 19]

from pathlib import Path Aufruf Arg. u. Variablen Ausgabe

Stack (in RAM)

def fstree(file, depth): fstree(root, 0) root root (26 Bytes)

s = [Link]().st_size 0 afile (15 Bytes)
41
print("...") adir (20 Bytes)
fstree(adir, 1) subdir (16 B.)
if file.is_dir(): adir
1 deepf (13 B.)
for f in [Link](): 20 file
s += fstree(f, depth+1) bdir
fstree(subdir, 2) subdir
return s 2 fileA
16 += fileB

size = fstree(Path('root'), 0) fstree(deepf, 3) deepf

print(f"Total: {size} Bytes") 3
13

Da es sich bei deepf um eine Datei handelt und nicht um ein Verzeichnis, kehrt dieser
Beispiel

Aufruf nun zurück, mit der Dateigröße als Rückgabewert.

13
 Traversierung des Verzeichnisbaums [Slide 20]

from pathlib import Path Aufruf Arg. u. Variablen Ausgabe

Stack (in RAM)

def fstree(file, depth): fstree(root, 0) root root (26 Bytes)

s = [Link]().st_size 0 afile (15 Bytes)
41
print("...") adir (20 Bytes)
fstree(adir, 1) subdir (16 B.)
if file.is_dir(): adir
1 deepf (13 B.)
for f in [Link](): 20 += file
s += fstree(f, depth+1) bdir
fstree(subdir, 2) subdir
return s 2 fileA
29 fileB

size = fstree(Path('root'), 0)
print(f"Total: {size} Bytes")

Der Aufrufer, fstree(subdir, 2), addiert diesen Rückgabewert zur Größe seines Ver-
Beispiel

zeichnisunterbaums hinzu. Da das Verzeichnis subdir neben deepf keine weiteren Ein-
träge enthält, kehrt fstree(subdir, 2) nun ebenfalls zurück.

Traversierung des Verzeichnisbaums [Slide 21]

from pathlib import Path Aufruf Arg. u. Variablen Ausgabe

Stack (in RAM)

def fstree(file, depth): fstree(root, 0) root root (26 Bytes)

s = [Link]().st_size 0 afile (15 Bytes)
41
print("...") adir (20 Bytes)
fstree(adir, 1) subdir (16 B.)
if file.is_dir(): adir
1 deepf (13 B.)
for f in [Link](): 49 file
s += fstree(f, depth+1) bdir
return s fileA
fileB

size = fstree(Path('root'), 0)
print(f"Total: {size} Bytes")

Der Aufrufer, fstree(adir, 1), addiert den Rückgabewert von fstree(subdir, 2) zur
Beispiel

Größe seines Verzeichnisunterbaums dazu.

14
 Traversierung des Verzeichnisbaums [Slide 22]

from pathlib import Path Aufruf Arg. u. Variablen Ausgabe

Stack (in RAM)

def fstree(file, depth): fstree(root, 0) root root (26 Bytes)

s = [Link]().st_size 0 afile (15 Bytes)
41
print("...") adir (20 Bytes)
fstree(adir, 1) subdir (16 B.)
if file.is_dir(): adir
1 deepf (13 B.)
for f in [Link](): 49 file
s += fstree(f, depth+1) bdir
fstree(file, 2)
return s fileA
fileB

size = fstree(Path('root'), 0)
print(f"Total: {size} Bytes")

Anschließend ruft er sich ein zweites Mal rekursiv auf, diesmal mit dem zweiten Ver-
Beispiel

zeichniseintrag von adir, nämlich file.

Traversierung des Verzeichnisbaums [Slide 23]

from pathlib import Path Aufruf Arg. u. Variablen Ausgabe

Stack (in RAM)

def fstree(file, depth): fstree(root, 0) root root (26 Bytes)

s = [Link]().st_size 0 afile (15 Bytes)
41
print("...") adir (20 Bytes)
fstree(adir, 1) subdir (16 B.)
if file.is_dir(): adir
1 deepf (13 B.)
for f in [Link](): 49 += file (9 Bytes)
s += fstree(f, depth+1) bdir
fstree(file, 2) file
return s 2 fileA
9 fileB

size = fstree(Path('root'), 0)
print(f"Total: {size} Bytes")

Dieser Aufruf gibt die Dateigröße von file zurück.

Beispiel

15
 Traversierung des Verzeichnisbaums [Slide 24]

from pathlib import Path Aufruf Arg. u. Variablen Ausgabe

Stack (in RAM)

def fstree(file, depth): fstree(root, 0) root root (26 Bytes)

s = [Link]().st_size 0 afile (15 Bytes)
41
print("...") += adir (20 Bytes)
fstree(adir, 1) subdir (16 B.)
if file.is_dir(): adir
1 deepf (13 B.)
for f in [Link](): 58 file (9 Bytes)
s += fstree(f, depth+1) bdir
return s fileA
fileB

size = fstree(Path('root'), 0)
print(f"Total: {size} Bytes")

fstree(adir, 1) hat nun seine sämtlichen Verzeichniseinträge abgearbeitet und kehrt

Beispiel

nun seinerseits zurück.

Traversierung des Verzeichnisbaums [Slide 25]

from pathlib import Path Aufruf Arg. u. Variablen Ausgabe

Stack (in RAM)

def fstree(file, depth): fstree(root, 0) root root (26 Bytes)

s = [Link]().st_size 0 afile (15 Bytes)
99
print("...") adir (20 Bytes)
subdir (16 B.)
if file.is_dir():
deepf (13 B.)
for f in [Link](): file (9 Bytes)
s += fstree(f, depth+1) bdir
return s fileA
fileB

size = fstree(Path('root'), 0)
print(f"Total: {size} Bytes")

fstree(root, 0) addiert den Rückgabewert von fstree(adir, 1) zur Größe seines

Beispiel

Verzeichnisunterbaums hinzu.
Es folgt der nächste rekursive Aufruf, nämlich fstree(bdir, 1). Wir brechen allerdings
an dieser Stelle ab, denn es dürfte klar geworden sein, wie die rekursive Aufrufstruktur von
fstree der rekursiven Struktur des Verzeichnisbaums folgt und wie die Rückgabewerte
der einzelnen Aufrufe verarbeitet werden.

16
 fstree(): Laufzeitanalyse (1) [Slide 26]

def fstree(file, depth):

size = [Link]().st_size
print(' ' ∗ depth ∗ 2 +
f"{[Link]} ({size} Bytes)")
if file.is_dir():
for f in [Link]():
size += fstree(f, depth + 1)
return size

Was ist die Laufzeit in Abhängigkeit von 𝑛, der Anzahl der Verzeichniseinträge
(Verzeichnisse + Dateien)?

• Bei jedem Aufruf von fstree() kann die for-Schleife maximal 𝑛 − 1 Mal
iterieren.
• Die Aufruftiefe ist maximal 𝑛.
• fstree() ist also 𝑂 (𝑛𝑛 ).

Formal korrekt, aber nicht eng.

Wie können wir das asymptotische Laufzeitverhalten von fstree als Funktion von 𝑛
Erklärung

bestimmen, der Gesamtzahl der Dateien und Verzeichnisse?

Gehen wir zunächst davon aus, dass alle Anweisungen bis auf for und den rekursiven
Aufruf in konstanter Zeit ablaufen.
Als ersten Versuch stellen wir nun fest, dass in einem gegebenen Aufruf die for-Schleife
nicht mehr als 𝑛 − 1 Mal iterieren kann. Zweitens ist klar, dass die Aufruftiefe 𝑛 nicht
übersteigen kann.
Gehen wir in beiden Fällen vom Maximalwert aus, dann enthält jeder rekursive Aufruf
𝑛 Iterationen, bis zu einer Rekursionstiefe von 𝑛. Damit haben wir eine Gesamtlaufzeit
von 𝑂(𝑛𝑛 ).
Diese Analyse ist zwar formal korrekt, aber sie überschätzt die maximale Gesamtlauf-
zeit gewaltig. Da wir insgesamt nur 𝑛 Verzeichniseinträge haben, können die maximale
Iterationszahl und die maximale Rekursionstiefe nicht gleichzeitig erreicht werden.

17
 fstree(): Laufzeitanalyse (2) [Slide 27]

Was ist die Laufzeit in Abhängigkeit von 𝑛, der Anzahl der Verzeichniseinträge
(Verzeichnisse + Dateien)?

root
• fstree() wird für jedes Element des Verzeichnisbaums
afile
exakt einmal (rekursiv) aufgerufen.
adir
• Dies gilt über alle rekursiven Aufrufe hinweg. Nicht alle subdir
Schleifen können Θ (𝑛) Iterationen durchlaufen, sondern die deepf
Gesamtzahl aller Iterationen ist Θ (𝑛). file
bdir
Der Aufrufbaum ist zum Dateibaum isomorph!
fileA
Der Aufrufbaum zeigt alle Aufrufe von (Kind-)Funktionen fileB
durch (Eltern-)Funktionen. Er muss hier nicht extra gezeich-
net werden, denn er entspricht exakt der eingerückten Dar-
stellung rechts.

• fstree() ist also Θ (𝑛).

Anmerkung

Dies ist ein Beispiel für amortisierte Laufzeitanalyse (siehe später):

Eine Analyse über mehrere Iterationen bzw. rekursive Aufrufe hinweg ermöglicht
die Bestimmung engerer Schranken als eine Analyse pro Iteration bzw. Aufruf.

Für eine enge und relevante Laufzeitanalyse kommt uns wiederum der Aufrufbaum zu
Erklärung

Hilfe. Die Struktur der Aufrufe folgt exakt der Struktur des Verzeichnisbaums. Mit ande-
ren Worten, der Aufrufbaum und der Verzeichnisbaum sind zueinander isomorph. Jedem
Verzeichniseintrag entspricht genau ein Aufruf von fstree. Damit ist die Gesamtlaufzeit
Θ(𝑛).

fstree(): Laufzeitanalyse (3) [Slide 28]

Ist die Laufzeit dieser Anweisung wirklich konstant:

print(' ' ∗ depth ∗ 2 + f"{[Link]} ({size} Bytes)")

• Wie könnte Python ' ' ∗ depth implementieren?

• Wie lange dauert die Ausgabe einer Zeichenkette auf dem Terminal?

Die Laufzeit von fstree() ist 𝑂(𝑛𝑑) für eine maximale Verschachtelungstiefe von
𝑑.

Bisher haben wir angenommen, dass alle Anweisungen bis auf for und den rekursiven
Erklärung

Aufruf in konstanter Zeit ablaufen. Wir müssen allerdings davon ausgehen, dass die
print-Anweisung für die Ausgabe der Einrückung eine lineare Zeit in depth benötigt.
Da diese Ausgabe bei jedem rekursiven Aufruf anfällt, multipliziert sich die Laufzeitkom-
plexität dieser Ausgabe mit der Anzahl der rekursiven Aufrufe. Daher ist die Laufzeit-
komplexität von fstree insgesamt 𝑂(𝑛𝑑), wenn die maximale Verschachtelungstiefe 𝑑
beträgt.

18
 Schlimmstenfalls besteht unsere Verzeichnisstruktur aus 𝑛 ineinander verschachtelten
Verzeichnissen. Damit hat depth beim ersten rekursiven Aufruf den Wert 1, beim zweiten
den Wert 2, usw. bis 𝑛. Die Gesamtdauer der print-Anweisungen ist also linear in der
Summe der Zahlen von 1 bis 𝑛, also 𝑂(𝑛2 ).

Quiz [Slide 29]

from pathlib import Path

def fstree(file, depth):

print(' ' ∗ depth ∗ 2 + [Link])
if file.is_dir():
for f in [Link]():
fstree(f, depth + 1)

fstree(Path('root'), 0)

Worin besteht hier der Rekursionsanfang?

A: Mehrfache Rekursion benötigt keinen Rekursionsanfang.

B: Der Aufruf fstree(Path('root'), 0) ist der Rekursionsanfang.

C: Der abwesende else-Zweig ist der Rekursionsanfang.

D: weiß nicht

4 Kombinationen

Kombinationen [Slide 30]

Alle Zeichenketten der Länge 𝑛 über einem Alphabet mit 𝑘 Zeichen:

𝑛 = 2, 𝑘 = 3 𝑛 = 3, 𝑘 = 2
AA AAA
AB AAB
AC ABA
BA ABB
BB BAA
BC BAB
CA BBA
CB BBB
CC

19
Kombinationen [Slide 31]

Idee: An jedes Zeichen des Alphabets hänge alle Kombinationen von 𝑛 − 1 Zeichen
an.
Algorithm combinations(𝑝, 𝑛):
Require: String head 𝑝 ( initially empty);
length 𝑛 of tail to generate .
Ensure: Displays a list of all length−𝑛 strings
under a 𝑘−letter alphabet 𝐴.
if 𝑛 > 0 then
for 𝑖 ← 1 to 𝑘 do
combinations(𝑝 + 𝐴[𝑖], 𝑛 − 1)
else
output 𝑝

Laufzeitanalyse:

• Bei jedem Funktionsaufruf wird die Schleife 𝑘 Mal durchlaufen.

• Jeder Schleifendurchlauf erzeugt einen rekursiven Aufruf.
• Die rekursive Aufruftiefe ist 𝑛.
• Der Aufrufbaum hat also 𝑘𝑛 Blätter, plus – da die Zahl der Knoten hier einer
geometrischen Reihe entspricht – insgesamt 𝑘𝑘−1 interne Knoten.
𝑛
−1

• Jedes Blatt gibt einen String der Länge 𝑛 aus.

• Benötigen alle anderen Anweisungen konstante Zeit, ist die Gesamtlaufzeit
also Θ (𝑛𝑘𝑛 ).

Die Mindestlaufzeit ergibt sich aus der Ausgabe eines Rechtecks von 𝑘𝑛 Zeilen und
𝑛 Spalten.

Kombinationen: Aufrufbaum [Slide 32]

k0 Knoten

k1 Knoten

2
k Knoten

kn–1 Knoten

kn Knoten

20
Endliche geometrische Reihe [Slide 33]
𝑛
∑ 𝑘𝑖 = 𝑘0 + 𝑘1 + ⋯ + 𝑘𝑛
𝑖=0
𝑛
(1 − 𝑘) ∑ 𝑘𝑖 = (1 − 𝑘) (𝑘0 + 𝑘1 + ⋯ + 𝑘𝑛 )
𝑖=0
= 𝑘0 + 𝑘1 + ⋯ + 𝑘𝑛 − 𝑘1 − 𝑘2 − ⋯ − 𝑘𝑛+1
= 𝑘0 − 𝑘𝑛+1
𝑛
𝑘0 − 𝑘𝑛+1
∑ 𝑘𝑖 =
𝑖=0
1−𝑘
𝑘𝑛+1 − 1
=
𝑘−1
Der Trick besteht hier in der Erstellung einer sogenannten Teleskopsumme.

Anmerkung
𝑛−1
∑ 2𝑖 = 2𝑛 − 1
𝑖=0

… wie jedem Informatiker durch das binäre Zahlensystem bekannt sein dürfte.

5 Eigenschaften

Konzepte [Slide 34]

• Rekursionsanfang
Ohne Rekursionsanfang wäre die Rekursion unendlich.

• Rekursionsschritt
Auch Sequenzen mehrerer Rekursionsschritte sind möglich (mehrfache Rekur-
sion).

Anmerkung

Jeder (rekursive) Aufruf verfügt über seine eigenen Parameter und lokalen Varia-
blen.

21
 Rekursion und Induktion [Slide 35]

Beide beruhen auf den gleichen Konzepten, verfahren jedoch in entgegengesetzte

Richtungen:
Induktionsschritt

Anfang

Rekursionsschritt
Anfang Schritt Sinn
Induktion Von hier geht alles aus. Zum nächsten Fall, Einfach zu
vom Anfang weg. beweisen.
Rekursion Hierauf wird alles Zum vorigen Fall, Einfach zu
zurückgeführt. zum Anfang hin. berechnen.

Iteration → Rekursion [Slide 36]

Video 4 beginnt hier.

Jede Iteration kann als Endrekursion (tail recursion) ausgedrückt werden: Die auf-
rufende Funktion kehrt unmittelbar nach Rückkehr des rekursiven Aufrufs zurück;
ein allfälliger Rückgabewert wird nicht weiter verarbeitet.
Algorithm factorial(𝑛): Algorithm factorial(𝑛):
Require: Integer 𝑛 ≥ 0. Require: Integer 𝑛 ≥ 0.
Ensure: Return 𝑛!. Ensure: Return 𝑛!.
𝑓 ←1 return factorial−rec(𝑛, 2, 1)
for 𝑖 ← 2 to 𝑛 do
𝑓 ← 𝑓𝑖 Algorithm factorial−rec(𝑛, 𝑖, 𝑓):
return 𝑓 Require: Integer 𝑛, 𝑓 ≥ 0;
integer counter 1 ≤ 𝑖 ≤ 𝑛 + 1.
Ensure: Return 𝑖!.
if 𝑖 > 𝑛 then
return 𝑓
else
return factorial−rec(𝑛, 𝑖 + 1, 𝑓𝑖)

Endrekursion bedeutet, dass ein rekursiver Aufruf das letzte ist, was in einer Funktion
Definition

passiert. Falls dieser Aufruf einen Rückgabewert liefert, wird dieser unmittelbar zurück-
gegeben.
Jede Iteration lässt sich als Endrekursion ausdrücken. Jede Iteration der Schleife ent-
spricht einem rekursiven Aufruf, wobei der Zähler, seine obere Schranke, und das Ergeb-
nis der Berechnung als Argumente übergeben werden.
Der tiefste rekursive Aufruf berechnet also das Ergebnis der letzten Iteration. Dieses Er-
gebnis wird dann als Rückgabewert von allen Aufrufen bis zum ersten Aufruf unverändert
durchgereicht.
Sehen wir hier links noch einmal unsere iterative factorial-Funktion. Die Laufvariable
𝑖 läuft von 1 bis 𝑛, und das Ergebnis der Berechnung jeder Iteration wird in 𝑓 gespeichert.
Rechts unten sehen wir die entsprechende Formulierung als Endrekursion. Die Funktion
factorial−rec übernimmt die drei Variablen 𝑛, 𝑖 und 𝑓 als Parameter. Als erstes wird
die Schleifenbedingung getestet. Falls diese nicht mehr wahr ist, ist das Ergebnis in 𝑓
bereits vollständig berechnet und wird sofort zurückgegeben.

22
 Andernfalls findet der nächste Berechnungsschritt statt, indem das Teilergebnis 𝑓 mit der
Laufvariablen 𝑖 multipliziert und die Laufvariable inkrementiert wird. Die Ergebnisse
werden als Argumente dem nächsten rekursiven Aufruf übergeben und werden somit
dessen Parametern 𝑓 und 𝑖 zugewiesen.
Nun benötigen wir lediglich noch eine Funktion, die die rekursive Prozedur mit den
korrekten Anfangsparametern startet. Die Funktion factorial oben rechts übergibt die
Anfangswerte 𝑖 = 2 und 𝑓 = 1, analog zum iterativen Algorithmus links.

Rekursion → Iteration [Slide 37]

Jede Rekursion kann als Iteration ausgedrückt werden; unmittelbar (und automati-
sierbar) bei Endrekursion.
Andernfalls verwendet man explizit einen oder mehrere Stapel (stack).

Algorithm reverseArray(𝐴, 𝑖, 𝑗): 0 1 2 3 4 5 6 7

Require: Array 𝐴 and indices 𝑖, 𝑗 ≥ 0. 8 5 2 7 6 9 1 3
Ensure: Reversal of elements in 𝐴
from 𝑖 to 𝑗. 3 5 2 7 6 9 1 8
if 𝑖 < 𝑗 then
swap 𝐴[𝑖] and 𝐴[𝑗]
3 1 2 7 6 9 5 8
reverseArray(𝐴, 𝑖 + 1, 𝑗 − 1)
3 1 9 7 6 2 5 8
reverseArray(𝐴, 0, 7)

3 1 9 6 7 2 5 8

Umgekehrt kann jede Rekursion als Iteration ausgedrückt werden. Im Allgemeinen benö-
Erklärung

tigt man hierfür Hilfsdatenstrukturen. Dies wäre z.B. bei unserem fstree-Algorithmus
der Fall.
Endrekursion kann jedoch unmittelbar und automatisierbar als Iteration ausgedrückt
werden, indem der umgekehrte Weg gegangen wird wie zuvor beschrieben. Jede Rekur-
sion hat einen Anfang. Dieser wird zur Abbruchbedingung der Schleife. Werte, die sich
von einem rekursiven Aufruf zum nächsten ändern, ändern sich entsprechend von einer
Schleifeniteration zur nächsten.
In unserem Beispiel invertiert reverseArray das Array 𝐴, indem es das erste und das
letze Element vertauscht und danach sich selbst auf dem verbleibenden Unterarray zwi-
schen diesen beiden Elementen aufruft. Es ist eine einfache Übung, diesen rekursiven
Algorithmus in einen iterativen zu überführen.

23
Formen von Rekursion [Slide 38]

• lineare Rekursion (linear recursion)

Maximal ein rekursiver Aufruf (s.o.).
• mehrfache Rekursion (multiple recursion)
Mehrere rekursive Aufrufe (s.o.).
• Endrekursion (tail recursion)
Nichts folgt nach dem rekursiven Aufruf (s.o.).
• wechselseitige Rekursion (mutual recursion)
Mehrere Funktionen rufen sich derart gegenseitig auf, dass von mindestens
einer davon mehrere Instanzen gleichzeitig (auf dem Aufrufstapel) aktiv sind
(s.u.).

Wechselseitige Rekursion [Slide 39]

Algorithm isEven(𝑛): Algorithm isOdd(𝑛):

Require: Integer 𝑛 ≥ 0. Require: Integer 𝑛 ≥ 0.
Ensure: Return true if 𝑛 even; Ensure: Return true if 𝑛 odd;
false if 𝑛 odd. false if 𝑛 even.
if 𝑛 = 0 then if 𝑛 = 0 then
return true return false
else else
return isOdd(𝑛 − 1) return isEven(𝑛 − 1)

Selbstverständlich würde niemand ernsthaft einen Test auf Geradzahligkeit auf

diese Weise implementieren, die in mehrfacher Hinsicht sehr ineffizient ist.

Wechselseitige Rekursion: Praktisches Beispiel [Slide 40]

Rekursiver Abstieg:

• Jedem Nichtterminalsymbol (linke Seite jeder Produktionsregel der Gramma-

tik) entspricht eine Methode des Parsers.
• Diese Methoden rufen sich entsprechend der Produktionsregeln (rechte Seite)
gegenseitig auf.

expression → term { + term }

term → factor { × factor }
factor → identifier | ( expression )

𝑎
⏟ ×( ⏟𝑏 + ⏟𝑐 )
⏟
factor
factor ⏟factor
⏟⏟⏟⏟⏟
term term
⏟⏟⏟ expression
⏟⏟⏟⏟
⏟⏟⏟⏟⏟⏟⏟⏟⏟ factor
⏟⏟⏟⏟⏟⏟⏟⏟⏟
term
expression

24
Ineffiziente Rekursion: unique3() [Slide 41]

Algorithm unique3(𝑆, 𝑙, ℎ):

Require: Sequence 𝑆, indizes 𝑙 (low) and ℎ (high).
Ensure: Return true iff all elements of the subsequence
𝑆[𝑙, … , ℎ] are unique.
if (𝑙 ≥ ℎ) return true
if (not unique3(𝑆, 𝑙, ℎ − 1)) return false
if (not unique3(𝑆, 𝑙 + 1, ℎ)) return false
return 𝑆[𝑙] ≠ 𝑆[ℎ]

• Jeder Aufruf löst zwei weitere Aufrufe aus,

• bis zu einer Rekursionstiefe von 𝑛 − 1.
• Es finden also 1 + 2 + 4 + 8 + ⋯ + 2𝑛−1 = 2𝑛 − 1 Aufrufe statt.
• Da alle anderen Anweisungen in konstanter Zeit ablaufen, ist
unique3(𝑆, 0, 𝑛 − 1) 𝑂 (2𝑛 ).

Ineffiziente Rekursion: Fibonacci() [Slide 42]

𝐹0 = 0, 𝐹1 = 1, 𝐹𝑘 = 𝐹𝑘−2 + 𝐹𝑘−1
Algorithm Fibonacci(𝑘):
Require: Integer 𝑘 ≥ 0.
Ensure: Return the 𝑘−th Fibonacci number.
if 𝑘 ≤ 1 then
return 𝑘
return Fibonacci(𝑘 − 2) + Fibonacci(𝑘 − 1)

Die Laufzeitanalyse ist ähnlich wie bei unique3().

Warnung

Rekursive Definitionen können ineffizienten Algorithmen entsprechen!

Fibonacci: effiziente, lineare Rekursion [Slide 43]

Algorithm Fibonacci(𝑘):
Require: Integer 𝑘 ≥ 0.
Ensure: Return the pair of Fibonacci numbers (𝐹𝑘 , 𝐹𝑘−1 ).
if 𝑘 ≤ 1 then
return (𝑘, 0)
else
(𝑖, 𝑗) ←Fibonacci(𝑘 − 1)
return (𝑖 + 𝑗, 𝑖)

Θ (𝑘)

25
6 Zusammenfassung

Zusammenfassung [Slide 44]

• Für viele Probleme existieren rekursive Algorithmen, die deutlich simpler sind
als nicht-rekursive Algorithmen.

• Einfach (für den Leser des Codes) impliziert jedoch nicht immer effizient (Be-
darf an Runtime-Ressourcen):

– Die Laufzeit kann explodieren.

– Jeder rekursive Aufruf verbraucht Speicherplatz auf dem Aufrufstapel.
– Funktionsaufrufe sind aufwändiger als Schleifensprünge.

• Rekursion und Induktion beruhen auf denselben Konzepten (Anfang und Schritt),
aber verfahren in entgegengesetzte Richtungen.

• Zur Laufzeitanalyse eines rekursiven Algorithmus ist der Aufrufbaum oft sehr
nützlich.

• Jede Iteration kann (einfach) als Endrekursion ausgedrückt werden, und jede
Rekursion kann (ggf. unter expliziter Verwendung von Stapeln) als Iteration
ausgedrückt werden.

26