# 3.5 Rekursion

Quelle: https://inf.zone/lectures/3-algorithmen/short-3-5-rekursion/

## Video

[Video ansehen (1080p)](https://videos.inf.zone/14462c7c57741855/short-3-5-rekursion-1080p.mp4) · [Video (720p)](https://videos.inf.zone/14462c7c57741855/short-3-5-rekursion-720p.mp4) · [Video (480p)](https://videos.inf.zone/14462c7c57741855/short-3-5-rekursion-480p.mp4) · [Video auf YouTube](https://youtu.be/xcLaoLYb65Y)

## Hinweise zu diesem Video

**Korrekturen**

Die Korrekturen betreffen das Video. In den Folien zum Herunterladen sind sie eingearbeitet, soweit sie die Folien betreffen.

- Folien 11 bis 13: Die rekursive Funktion fact hat nur den Basisfall n == 1; für n = 0 ruft sie sich ohne Ende selbst auf, während die iterative fact2 dort 1 liefert. Richtig ist der Basisfall „if (n <= 1) return 1;“, dann verhalten sich beide gleich.
- Ton zu den Folien 7 bis 9: Mit dem Typ int läuft schon 13! über, in einen 64-Bit-Typ passt 20! noch. Ton zu Folie 18: Der Überlauf entsteht beim Berechnen des Arguments 3\*n + 1, nicht beim Rückgabewert der Funktion.
- Folien 20 und 21: In der Funktion add fehlt die Deklaration von result; gemeint ist: int result = x + y; return result; Außerdem muss add vor add\_two stehen (oder vorab deklariert sein), sonst kennt der Compiler add beim Aufruf noch nicht.

**Einordnung**

- Im Video heißt es, die Extra-Minuten seien immer für fortgeschrittene Konzepte da. Das gilt nicht für jedes Short: Was aus den Extra-Minuten zur Basis gehört, steht jeweils auf der Seite des Shorts.

## Material

- [Folien](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf)
- Folien und Transkript: unten auf dieser Seite

## Folien und Transkript

*Folientext aus den PDF-Folien, darunter jeweils der gesprochene Text des Videos. Der gesprochene Text ist maschinell transkribiert und nachkorrigiert, kann aber noch Fehler enthalten; im Video sprechen abwechselnd Prof und eine AI-Figur, die Sprecherwechsel sind nicht markiert. Die Zuordnung zu den Folien ist ungefähr. Die Zeitangaben verlinken auf die Stelle im Video (YouTube). Maßgeblich sind Video und Folien.*

### Folie 1 — Rekursion

[Folie 1 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=1)

#### Transkript

**[Video 00:00–00:35](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=0)**

Dies ist Inf-Einf-B. Heute Rekursion. Ah, da bist du ja. Bereit für unsere Vorlesung über Rekursion? Natürlich. Ich freue mich besonders auf dieses Thema. Weißt du, Rekursion ist wie Poesie in Codeform. Oh nee. Bitte nicht schon wieder so philosophische Ausschweifungen heute. Keine Sorge.

### Folie 2

[Folie 2 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=2)

Eine Implementierung eines Algorithmus bezeichnen wir als besonders elegant, wenn sie ein Problem auf eine interessante und leicht visualisierbare Art löst.

Die Technik der Rekursion ist eine sehr verbreitete Methode, um eine solche elegante Lösung zu implementieren.

Die Definition einer rekursiven Funktion ist, dass sie sich im Rahmen ihrer Ausführung selbst aufruft.

#### Transkript

**[Video 00:00–00:35](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=0)**

Aber lass mich einen wichtigen Tipp für die Studierenden geben. Bei algorithmischen Konzepten wie Rekursion ist es hilfreich, kleine Beispiele auf Papier durchzuspielen. Ja, auf jeden Fall. Aber jetzt fangen wir an mit dem Thema. Programmcode erfüllt nicht nur einen Zweck.

**[Video 00:35–01:06](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=35)**

Wenn Sie eine Weile programmieren, werden Sie feststellen, dass Code auch schön sein kann. Wenn Code schön ist, dann löst er ein Problem besonders elegant. Oder die Struktur hat etwas Faszinierendes an sich. Rekursion ist eine solche elegante Methode, die Probleme oft auf überraschend kompakte und ansprechende Weise löst. Lassen Sie uns zunächst klären, was wir unter Eleganz im Kontext von Algorithmen verstehen. Eine Lösung bezeichnen wir als elegant, wenn sie nicht nur funktioniert, sondern auch leicht nachvollziehbar ist und eine gewisse ästhetische Qualität besitzt.

**[Video 01:06–01:34](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=66)**

Bei einer rekursiven Funktion ruft sich die Funktion selbst auf. Das mag zunächst seltsam klingen, aber Sie werden gleich sehen, wie effektiv diese Technik ist.

### Folie 3

[Folie 3 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=3)

Fakultäts-

Die Fakultät n! ist für alle positiven ganzen Zahlen definiert.

funktion

n! ist das Produkt aller positiven ganzen Zahlen kleiner oder gleich n.

Beim Programmieren nennen wir die mathematische Funktion n! oft `fact(n)`.

#### Transkript

**[Video 01:06–01:34](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=66)**

Betrachten wir die Fakultätsfunktion als erstes Beispiel für Rekursion. Die Fakultät einer Zahl n, geschrieben als n!, ist das Produkt aller positiven ganzen Zahlen bis einschließlich n. Also ist fünf Fakultät gleich fünf mal vier mal drei mal zwei mal eins. Das ergibt einhundertzwanzig. In der Programmierung nennen wir diese Funktion typischerweise fact von n.

**[Video 01:34–02:08](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=94)**

Vielleicht noch ein Hinweis zur praktischen Bedeutung der Fakultät.

### Folie 4 — Rekursion bei der Fakultätsfunktion

[Folie 4 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=4)

```text
fact(1) = 1
fact(2) = 2 * 1
fact(3) = 3 * 2 * 1
fact(4) = 4 * 3 * 2 * 1
fact(5) = 5 * 4 * 3 * 2 * 1
```

#### Transkript

**[Video 01:34–02:08](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=94)**

Die Fakultät spielt eine zentrale Rolle in der Statistik.

### Folie 5 — Rekursion bei der Fakultätsfunktion

[Folie 5 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=5)

```text
fact(1) = 1
fact(2) = 2 * fact(1)
fact(3) = 3 * 2 * 1
fact(4) = 4 * 3 * 2 * 1
fact(5) = 5 * 4 * 3 * 2 * 1
```

#### Transkript

**[Video 01:34–02:08](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=94)**

Wenn man zum Beispiel n verschiedene Zahlen hat und wissen will, wie viele unterschiedliche Anordnungen möglich sind, also die Anzahl der Permutationen ausrechnen möchte, dann ist die Antwort genau n Fakultät. Bei fünf Zahlen gibt es also 120 verschiedene Möglichkeiten, diese fünf Zahlen anzuordnen. Schauen wir uns die Berechnung der Fakultät im Detail an. Für n gleich eins ist das Ergebnis einfach eins. Für n gleich zwei multiplizieren wir zwei mit eins. Bei n gleich drei multiplizieren wir drei mit zwei und eins. Sehen Sie das Muster?

**[Video 02:08–02:41](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=128)**

Mit jeder größeren Zahl multiplizieren wir einfach diese neue Zahl mit dem vorherigen Ergebnis. Hier fällt etwas Interessantes auf: fact von 1 ist unser einfachster Fall. Wir müssen hier nichts multiplizieren, sondern geben einfach 1 zurück. In der Rekursion nennen wir das den Basisfall. Aber dazu kommen wir gleich. Diese schrittweise Zerlegung in kleinere Teilprobleme ist übrigens ein fundamentales Konzept der Informatik. Was wir hier bei der Fakultät ganz gut sehen, lässt sich auch auf viele komplexere Probleme übertragen. Wir reduzieren ein Problem so lange, bis wir einen trivialen Fall erreichen. In diesem Fall eben fact.

**[Video 02:41–03:04](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=161)**

Fakultät von eins. Jetzt wird es spannend. Betrachten Sie fact von zwei. Statt zwei mal eins können wir auch schreiben zwei mal fact von eins. Das erscheint vielleicht trivial, ist aber der Schlüssel zum Verständnis der Rekursion. Wir nutzen die Funktion fact in ihrer eigenen Definition. Was wir hier sehen, ist ein klassisches Beispiel für die Abstraktion eines Problems. Anstatt die gesamte Multiplikation explizit aufzuschreiben,

**[Video 03:04–03:43](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=184)**

formulieren wir das Problem einfach in Bezug auf eine bereits bekannte Lösung. Wenn wir die Fakultät von zwei kennen, dann können wir Fakultät von drei leicht ausrechnen. Wir müssen eben nur mit drei multiplizieren. Und hier sehen wir nun das vollständige rekursive Muster. Jede Berechnung von fact n basiert auf fact n minus eins. Dies führt uns zu einer erstaunlich kompakten allgemeinen Formel. fact von n ist gleich n mal fact von n minus eins. Diese einfache Formel beschreibt die gesamte Fakultätsfunktion. Vorausgesetzt, wir definieren noch den Basisfall. fact von eins ist eins.

### Folie 6 — Rekursion bei der Fakultätsfunktion

[Folie 6 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=6)

```text
fact(1) = 1
fact(2) = 2 * fact(1)
fact(3) = 3 * fact(2)
fact(4) = 4 * 3 * 2 * 1
fact(5) = 5 * 4 * 3 * 2 * 1
```

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 03:04–03:43](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=184)**

Ein wichtiger Hinweis zur Implementierung: Obwohl die mathematische Definition elegant ist, müssen wir bei der praktischen Umsetzung schon die Grenzen des Computers auf

### Folie 7 — Rekursion bei der Fakultätsfunktion

[Folie 7 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=7)

```text
fact(1) = 1
fact(2) = 2 * fact(1)
fact(3) = 3 * fact(2)
fact(4) = 4 * fact(3)
fact(5) = 5 * 4 * 3 * 2 * 1
```

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 03:43–04:14](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=223)**

Die Fakultät wächst ja sehr schnell.

### Folie 8 — Rekursion bei der Fakultätsfunktion

[Folie 8 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=8)

```text
fact(1) = 1
fact(2) = 2 * fact(1)
fact(3) = 3 * fact(2)
fact(4) = 4 * fact(3)
fact(5) = 5 * fact(4)
```

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 03:43–04:14](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=223)**

Bereits 20 Fakultät ist eine so enorm große Zahl, dass sie nicht mehr in den ganzzahligen Datentyp reinpasst.

### Folie 9 — Rekursion bei der Fakultätsfunktion

[Folie 9 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=9)

```text
fact(1) = 1
fact(2) = 2 * fact(1)
fact(3) = 3 * fact(2)
fact(4) = 4 * fact(3)
fact(5) = 5 * fact(4)
fact(n) = n * fact(n-1)
```

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 03:43–04:14](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=223)**

In der Praxis müssen wir also schon auch immer die Größenbeschränkungen von unseren Datentypen mitbedenken.

### Folie 10 — Zwei Fälle

[Folie 10 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=10)

Jede rekursive Funktion implementiert zwei mögliche Fälle:

1. den Basisfall, der die Rekursion beendet;

2. den rekursiven Fall, in dem die eigentliche Rekursion stattfindet.

#### Transkript

**[Video 03:43–04:14](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=223)**

Bei einer rekursiven Funktion benötigen wir immer zwei wesentliche Komponenten. Erstens den Basisfall, manchmal auch Abbruchbedingung genannt, der die Rekursion beendet. Zweitens den rekursiven Fall, bei dem die Funktion sich selbst mit veränderten Parametern aufruft.

### Folie 11 — Rekursion bei der Fakultätsfunktion

[Folie 11 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=11)

```text
fact(1) = 1
```

```c
int fact(int n)
{
    // Basisfall
    if (n <= 1)
    {
        return 1;
    }
    
    // Rekursiver Fall …
}
```

#### Transkript

**[Video 03:43–04:14](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=223)**

Der Basisfall ist hier einfach. Wenn n gleich eins ist, geben wir eins zurück.

**[Video 04:14–04:36](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=254)**

Das ist der einfachste Fall unserer Fakultätsfunktion. Im rekursiven Fall multiplizieren wir n mit dem Ergebnis von fact von n minus eins. Die Funktion ruft sich also selbst auf, aber mit einem kleineren Parameter. Das ist das Kernprinzip der Rekursion. Wir reduzieren das Problem schrittweise, bis wir den Basisfall erreichen. Diese Version ist noch kompakter, aber funktional identisch. Die geschweiften Klammern können wir weglassen.

**[Video 04:36–05:09](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=276)**

da wir nur eine einzelne Anweisung pro Zweig haben.

### Folie 12 — Rekursion bei der Fakultätsfunktion

[Folie 12 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=12)

```text
fact(n) = n * fact(n-1)
```

```c
int fact(int n)
{
    // Basisfall
    if (n <= 1)
    {
        return 1;
    }
    // Rekursiver Fall
    else
    {
        return n * fact(n-1);
    }
}
```

```c
int fact(int n)
{
    if (n <= 1)
        return 1;
    else
        return n * fact(n-1);
}
```

#### Transkript

*Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.*

### Folie 13 — Iterative Variante

[Folie 13 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=13)

```text
fact(n) = n * fact(n-1)
```

```c
int fact2(int n)
{
    int product = 1;
    while(n > 0)
    {
        product *= n;
        n--;
    }
    return product;
}
```

> Bildinhalte sind nicht transkribiert; siehe Originalfolie.

#### Transkript

**[Video 04:36–05:09](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=276)**

Lassen Sie uns die rekursive und die iterative Lösung gegenüberstellen. Beide Ansätze lösen dasselbe Problem, aber auf unterschiedliche Weise. Die iterative Version verwendet eine Schleife und eine Variable, um das Produkt schrittweise zu berechnen. Sie ist möglicherweise einfacher zu verstehen für Programmierer, die mit traditionellen Schleifenkonstrukten vertraut sind. Ein interessanter Aspekt, den wir hier sehen: Die iterative Version benötigt expliziten Speicher für die Zwischenergebnisse, die Variable product.

### Folie 14

[Folie 14 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=14)

Besondere Fälle

Meistens, aber nicht immer, ersetzen rekursive Funktionen Schleifen in nichtrekursiven Funktionen.

Es ist auch möglich, mehr als einen Basisfall oder mehr als einen Rekursionsfall zu haben.

Beispiele: Fibonacci-Zahlen, Collatz-Vermutung

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 04:36–05:09](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=276)**

Die rekursive Version versteckt den Speicherbedarf in den Funktionsaufrufen auf dem Stack.

**[Video 05:09–05:40](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=309)**

In der Praxis kann es bei sehr tiefer Rekursion zu so einem sogenannten Stack Overflow führen. Ein klassischer Trade-Off zwischen Eleganz und praktischen Limitierungen. Moment mal, gab es nicht hier im Raum irgendjemand, der in früheren Videos immer betont hat, dass wir keine Konzepte verwenden sollen, die die Studierenden noch nicht kennen? Stack, Stack Overflow, ernsthaft? Ja, jetzt hast du mich mal erwischt. Das war vielleicht etwas voreilig. Sollen wir vielleicht? Ja, ich könnte jetzt kurz erklären. Also, wenn man, wenn eine Funktion sich selbst aufruft, dann

**[Video 05:40–06:04](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=340)**

Nein, das wird jetzt an der Stelle glaube ich einfach zu komplex. Darf ich einen Vorschlag machen? Wir haben doch am Ende der Vorlesung immer die drei Extra Minuten für fortgeschrittene Konzepte. Das wäre der perfekte Zeitpunkt, um über Funktionsaufrufe und Speicherverwaltung zu sprechen. Ja, das ist eine gute Idee. Bleiben wir für den Moment einfach bei der Rekursion und bleiben dabei, dass das praktischer und eleganter aussieht. Und die Details können wir uns ja dann in den drei Extra Minuten anschauen.

### Folie 15

[Folie 15 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=15)

Fibonacci-Folge

Die Fibonacci-Folge ist wie folgt definiert:

Das erste Element ist 0.

Das zweite Element ist 1.

Das n-te Element ist die Summe der Elemente (n–1) und (n–2).

#### Transkript

**[Video 06:04–06:35](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=364)**

Kommen wir zu einem Beispiel, bei dem man mehr als einen Basisfall benötigt: die Fibonacci-Folge. Diese Zahlenfolge taucht überraschenderweise häufig in der Natur auf, zum Beispiel in der Anordnung von Blütenblättern oder im Wachstumsmuster von Schneckenhäusern. Aber konzentrieren wir uns auf die mathematische Definition. Wir beginnen mit 0 und 1. Jede weitere Zahl ist dann einfach die Summe ihrer beiden Vorgänger. Die Fibonacci-Folge ist tatsächlich ein exzellentes Beispiel für den Unterschied zwischen einer eleganten mathematischen Definition und einer effizienten Implementierung.

**[Video 06:35–07:07](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=395)**

Die rekursive Lösung ist zwar wunderschön kurz, aber für größere n extrem ineffizient, weil sie einfach viele Berechnungen mehrfach durchführt.

### Folie 16 — Die Collatz-Vermutung

[Folie 16 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=16)

Die Collatz-Vermutung gilt für positive ganze Zahlen. Es wird vermutet, dass man immer „zurück zur 1“ kommt, wenn man folgende Schritte befolgt:

Wenn n = 1, gib 1 zurück.

Sonst:

wenn n gerade ist, gib n / 2 zurück;

wenn n ungerade ist, gib 3n + 1 zurück.

Wir könnten eine rekursive Funktion c(n) schreiben, die berechnet, wie viele Schritte man braucht, um zur 1 zu gelangen, wenn man bei n beginnt.

#### Transkript

**[Video 06:35–07:07](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=395)**

In der Praxis würde man das wahrscheinlich eher iterativ implementieren. Nun kommen wir zu einem mathematischen Problem mit mehreren rekursiven Fällen: der Collatz-Vermutung. Diese Vermutung ist bis heute unbewiesen. Die mathematischen Details müssen Sie natürlich nicht kennen. Die Collatz-Vermutung schauen wir uns hier vor allem deswegen an, weil es hier eine interessante rekursive Implementierung gibt. Das Besondere daran ist, dass wir abhängig von der Eingabe

**[Video 07:07–07:38](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=427)**

unterschiedliche rekursive Aufrufe haben. Betrachten wir einige konkrete Beispiele. Die Funktion Collatz von n gibt die Anzahl der Schritte zurück, die benötigt werden, um von n zu 1 zu gelangen. Für n gleich 1 brauchen wir null Schritte.

### Folie 17 — c(n): Anzahl der Schritte bis zur 1

[Folie 17 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=17)

```text
 n  c(n)  Schritte
 1    0   1
 2    1   2 1
 3    7   3 10 5 16 8 4 2 1
 4    2   4 2 1
 5    5   5 16 8 4 2 1
 6    8   6 3 10 5 16 8 4 2 1
 7   16   7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
 8    3   8 4 2 1
15   17   15 46 23 70 … 8 4 2 1
27  111   27 82 41 124 … 8 4 2 1
50   24   50 25 76 38 … 8 4 2 1
```

Implementieren Sie c(n).

#### Transkript

**[Video 07:07–07:38](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=427)**

Wir sind ja schon am Ziel. Für n gleich 2 brauchen wir einen Schritt. 2 ist gerade, also teilen wir durch 2 und erreichen 1. Bei n gleich 3 wird es interessanter. 3 ist ungerade, also berechnen wir 3 mal 3 plus 1, was 10 ergibt, dann 10 durch 2, also 5, dann 16, 8, 4, 2, 1. Insgesamt sieben Schritte.

**[Video 07:38–08:11](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=458)**

Was hier besonders auffällig ist, die Anzahl der Schritte scheint keinem offensichtlichen Muster zu folgen. Bei n gleich sieben brauchen wir sogar 16 Schritte, und die Zahlen steigen zwischendurch bis auf 52, bevor sie wieder fallen. Dieses scheinbar chaotische Verhalten ist auch einer der Gründe, warum die Vermutung so schwer zu beweisen ist. So, jetzt sind Sie dran. Pausieren Sie das Video und versuchen Sie, die Funktion Collatz von n selbst zu implementieren. Denken Sie an die Struktur, die wir bei der Fakultät gesehen haben. Am besten überlegen Sie sich zuerst den Basisfall, also fragen sich, wann hören wir auf? Dann müssen Sie sich die zwei rekursiven Fälle überlegen.

**[Video 08:11–08:48](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=491)**

Was passiert bei geraden, ungeraden Zahlen? Dabei nicht vergessen: Die Funktion soll die Anzahl der Schritte zurückgeben. Und denken Sie daran: Testen Sie Ihre Implementierung mit den Beispielen aus der Tabelle. Wenn Sie für n gleich drei nicht auf sieben Schritte kommen, haben Sie wahrscheinlich einen Fehler gemacht. Hier ist die Lösung.

### Folie 18 — Lösung

[Folie 18 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=18)

```c
int collatz(int n)
{
    // base case
    if (n == 1)
        return 0;
    // even numbers
    else if ((n % 2) == 0)
        return 1 + collatz(n/2);
    // odd numbers
    else
        return 1 + collatz(3*n + 1);
}
```

#### Transkript

*Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.*

### Folie 19

[Folie 19 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=19)

E X T R A S I N 3 M I N U T E N FRAGEN – ANTWORTEN – RÄTSEL UND KURZE ZUSAMMENFASSUNG

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 08:11–08:48](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=491)**

Schauen wir uns die drei wichtigen Teile an. Der Basisfall ist einfach.

### Folie 20 — Entscheidungsproblem zur Laufzeit

[Folie 20 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=20)

```text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
```

```c
int add(int x, int y) {
    return x + y; // Wo geht es weiter:
}                 // in add_two oder mult?

int add_two(int x) {
    return add(x, 2);
}

int mult(int x, int y) {
    int sum = 0;
    for(int i = 0; i < y; i++) {
        sum = add(sum, x);
    }
    return sum;
}

int main() {
    int a = 5, b = 3;
    int result = mult(a, b);
    printf("%d", result);
    return 0;
}
```

#### Transkript

*Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.*

### Folie 21 — Lösung: Call Stack im Speicher

[Folie 21 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=21)

```text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
```

```c
int add(int x, int y) {
    return x + y; // ← hier sind wir
}

int add_two(int x) {
    return add(x, 2);
}

int mult(int x, int y) {
    int sum = 0;
    for(int i = 0; i < y; i++) {
        sum = add(sum, x);
    }
    return sum;
}

int main() {
    int a = 5, b = 3;
    int result = mult(a, b);
    printf("%d", result);
    return 0;
}
```

```text
Speicher
|--------------------|
| add:               | ← Aktueller
| x = 0, y = 5       |    Frame
| Return → mult     |
|--------------------|
| mult:              | ← Rief
| x = 5, y = 3       |    add auf
| sum = 0, i = 0     |
| Return → main     |
|--------------------|
| main:              | ← Rief
| a = 5, b = 3       |    mult auf
| result = __        |
|--------------------|
```

#### Transkript

**[Video 08:11–08:48](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=491)**

Wenn wir eins erreichen, geben wir null zurück, da keine weiteren Schritte mehr nötig sind. Bei geraden Zahlen teilen wir durch zwei und bei ungeraden multiplizieren wir mit drei und addieren eins. Das plus eins in den Return-Anweisungen zählt jeweils den aktuellen Schritt mit. Ein wichtiger Hinweis zur Implementierung noch.

**[Video 08:48–09:06](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=528)**

Bei der Berechnung von 3n plus 1 sollten Sie auf Integerüberläufe achten. Bei größeren Zahlen kann.

### Folie 22 — Stack Overflow

[Folie 22 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=22)

```text
|--------------------|
| fact:              |
| n = 14752          |
| Return → fact     |
|--------------------|
| fact:              |
| n = 14753          |
| Return → fact     |
|--------------------|
…
|--------------------|
| fact:              |
| n = 50000          |
| Return → main     |
|--------------------|
| main:              |
| n = 50000          |
| result = __        |
|--------------------|
```

```text
-----

  ↑

  Für Stack  
  reservierter
  Speicherbereich

  ↓

-----
```

#### Transkript

**[Video 08:48–09:06](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=528)**

Was schaust du so? Was ein Integerüberlauf ist, habe ich doch schon in der Vorlesung erwähnt. Was denn? Du meinst, ich soll es noch mal erklären, weil es so lange her ist? Na gut. Also stellen Sie sich einfach einen 32-Bit-Integer vor.

**[Video 09:06–09:42](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=546)**

Der kann ja Zahlen bis etwa zwei Milliarden speichern. Wenn wir bei einer großen Zahl n mit drei multiplizieren und eins addieren, dann kann das Ergebnis kurzzeitig mal größer als zwei Milliarden werden. Es muss aber ja in einer int-Variable zwischengespeichert werden, weil die Funktion ja einen int zurückgibt. Beim Zwischenspeichern kommt es dann zum Überlauf und es wird dann ein falsches Ergebnis an die aufrufende Funktion zurückgegeben. Apropos Überläufe, hatten wir vorhin nicht schon über etwas anderes gesprochen, das überlaufen kann? Ja ja, der Stack. Machen wir einfach gleich mit den drei extra Minuten weiter. Da können wir in Ruhe klären, was bei einer Rekursion dann unter der Haube eigentlich passiert.

**[Video 09:42–10:16](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=582)**

So, kannst du den Studierenden mal den Call Stack erklären? Am besten mit einem aussagekräftigeren Beispiel. Natürlich. Schauen wir uns ein konkretes Beispiel an. Der Call Stack ist ein spezieller Bereich im Speicher des Programms. Beim Compilieren fügt der Compiler dem Programm Instruktionen hinzu, mit denen sich das Programm zur Laufzeit merkt, wie es in die gerade aktive Funktion hineingekommen ist und welche Variablen und Parameter dort deklariert wurden. Jedes Mal, wenn eine Funktion aufgerufen wird, legt der Compiler dazu einen neuen Stack Frame oben auf den Stapel. Dieser Frame enthält unter anderem Folgendes: Erstens

**[Video 10:16–10:39](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=616)**

die Parameter der aufgerufenen Funktion, zweitens Speicherplatz für alle Variablen, die lokal in der Funktion deklariert werden, und drittens die Rücksprungadresse, also quasi die Zeile, bei der es im Code weitergehen soll, wenn die Funktion fertig ist, also wieder verlassen wird. Wenn eine Funktion beendet wird, entfernt der Compiler ihren Frame und springt zur gespeicherten Rücksprungadresse. Was passiert jetzt bei einer rekursiven Funktion wie unserer Fakultät?

**[Video 10:39–11:09](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=639)**

nehmen wir fact von fünf, da stapeln sich die Frames. Und wenn wir statt fünf eine sehr große Zahl nehmen, dann bekommen wir einen Stack Overflow. Der Grund dafür ist, dass der Compiler beim Kompilieren des Programms nur eine begrenzte Menge Speicher für den Stack reserviert. Bei zu vielen verschachtelten Funktionsaufrufen ist dieser Speicher dann zur Laufzeit irgendwann einfach erschöpft. Legt das Programm dann einen weiteren Stack-Frame auf den Stack, überschreibt es Speicher, der dafür gar nicht vorgesehen ist, und das Programm wird vom Betriebssystem einfach ohne Vorwarnung sofort beendet.

**[Video 11:09–11:40](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=669)**

Das ist übrigens ein häufiger Fehler bei Anfängern in der Programmierung. Man schreibt eine schöne rekursive Funktion und wundert sich, warum das Programm bei großen Eingaben abstürzt. Genau. Zum Abschluss wäre vielleicht noch eine Denksportaufgabe schön, oder? Wir haben da etwas für Sie vorbereitet. Schauen Sie sich doch mal diesen Code an. Was berechnet diese Funktion? Tipp: Der Name der Funktion gibt bereits einen Hinweis darauf. Setzen Sie einfach ein paar kleine Zahlen ein und überlegen Sie, was das Ergebnis bedeuten könnte. Die Auflösung gibt es in der nächsten Vorlesung. Kleiner Scherz.

**[Video 11:40–12:07](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=700)**

Am Ende dieses Videos lassen Sie uns zum Abschluss noch einmal zusammenfassen, was Rekursion ist. Also Rekursion versteht man am besten, indem man versteht, wie man Rekursion versteht. Also indem man versteht, wie man Rekursion versteht. Also indem man versteht, wie man Rekursion versteht. Also indem man versteht. Hallo, sag mal, was ist denn hier der Basisfall? Dass Rekursion eine Funktion nutzt, die sich selbst aufruft, um ein Problem durch Reduktion auf einfachere Teilprobleme zu lösen.

**[Video 12:07–12:39](https://www.youtube.com/watch?v=xcLaoLYb65Y&t=727)**

Interessant. Wie lange hättest du denn jetzt noch weitergemacht, wenn ich dich nicht aus deiner Endlosschleife befreit hätte? Na, bis zum Stack Overflow halt. Oh. Dies war Inf-Einf-B.

### Folie 23 — Was berechnet dieses Programm?

[Folie 23 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=23)

```text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
```

```c
#include <stdio.h>

int waysToClimbStairs(int n);

int main(void)
{
    int n = 4;
    printf("Result for n = %d is %d\n", n, waysToClimbStairs(n));
    return 0;
}

int waysToClimbStairs(int n)
{
    if (n == 0 || n == 1)
        return 1;
    else
        return waysToClimbStairs(n - 1) +
               waysToClimbStairs(n - 2);
}
```

#### Transkript

*Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.*

### Folie 24 — Rekursion:

[Folie 24 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.5-rekursion.pdf#page=24)

Der rekursive Fall reduziert

Eine Funktion ruft sich

das Problem auf einen

selbst mit kleineren

einfacheren Fall.

Teilproblemen auf.

Jede rekursive Funktion

Rekursion ist oft eleganter

benötigt mindestens

als iterative Lösungen.

einen Basisfall.

Der Basisfall beendet die

Achtung: Rekursionstiefe durch Stackgröße begrenzt.

Rekursion und liefert ein

direktes Ergebnis.

> Bildinhalte sind nicht transkribiert; siehe Originalfolie.

#### Transkript

*Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.*