Rekursion — So funktioniert sie, mit Beispielen & Basisfällen

Rekursion in der Mathematik bedeutet, eine Funktion, Folge oder einen Prozess mithilfe kleinerer Fälle derselben Idee zu definieren. Eine rekursive Definition funktioniert nur, wenn sie einen Basisfall und eine Regel enthält, die jeden neuen Fall auf diesen Basisfall zubewegt.

Wenn du nur die Grundidee brauchst, dann ist es diese: Rekursion ist in dem Moment nicht mehr nützlich, in dem die Regel für kleinere Schritte keinen gültigen Endpunkt mehr erreicht.

Was Rekursion in der Mathematik bedeutet

Eine rekursive Definition listet nicht jeden Fall einzeln auf. Stattdessen gibt sie einen Startpunkt und eine Regel an, mit der größere Fälle aus kleineren aufgebaut werden.

Das unterscheidet sie von einer direkten Formel. Eine direkte Formel liefert die Antwort aus der Eingabe in einem einzigen Ausdruck. Eine rekursive Definition reduziert das Problem Schritt für Schritt, bis sie einen Fall erreicht, der bereits bekannt ist.

Warum ein Basisfall notwendig ist

Der Basisfall ist der Haltepunkt. Ohne ihn verweist die Definition immer weiter auf kleinere und kleinere Fälle, ohne jemals zu enden.

Der Basisfall muss außerdem zu der gewählten Regel passen. Wenn der rekursive Schritt von $n$ auf $n-1$ reduziert, dann muss der Basisfall für die zugelassenen Eingaben in diesem Muster erreichbar sein.

Durchgerechnetes Beispiel: Rekursion bei der Fakultät

Die Fakultät ist eine Standarddefinition für Rekursion. Für ganze Zahlen $n \ge 0$ definiert man die Fakultät durch

$$0! = 1$$

und für $n \ge 1$

$$n! = n(n-1)!$$

Hier ist $0! = 1$ der Basisfall, und $n! = n(n-1)!$ ist der rekursive Schritt.

Um $4!$ zu berechnen, reduziert man weiter, bis der Basisfall erscheint:

$$4! = 4 \cdot 3! = 4 \cdot 3 \cdot 2! = 4 \cdot 3 \cdot 2 \cdot 1! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0!$$

Nun wende den Basisfall $0! = 1$ an:

$$4! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 24$$

Das ist das vollständige Rekursionsmuster: auf einen kleineren Fall reduzieren, den Basisfall erreichen und dann zurück zur ursprünglichen Frage auswerten.

Rekursion vs. Rekursionsgleichung

Rekursion ist die allgemeinere Idee. Eine Rekursionsgleichung ist eine rekursive Regel für eine Folge, bei der jedes Glied von früheren Gliedern abhängt.

Zum Beispiel wird die Fibonacci-Folge durch eine Rekursionsgleichung beschrieben, weil jedes Glied aus früheren Gliedern definiert wird. Die Fakultät ist ebenfalls rekursiv, wird aber meist als rekursive Definition einer Funktion und nicht als Rekursion für eine Folge dargestellt.

Häufige Fehler bei Rekursion

Den Basisfall weglassen

Wenn es keinen Basisfall gibt, endet die Definition nicht.

Einen Schritt verwenden, der nicht kleiner wird

Wenn der rekursive Schritt nicht auf den Basisfall zugeht, kann der Prozess endlos weiterlaufen oder für manche Eingaben undefiniert werden.

Die Bedingung der Regel vergessen

Im Fakultäts-Beispiel wird die Regel $n! = n(n-1)!$ für $n \ge 1$ verwendet. Diese Bedingung ist wichtig. Ohne sie könnte man versuchen, die Regel dort anzuwenden, wo die Definition gar nicht gedacht ist.

Annehmen, Rekursion sei nur eine Idee aus der Programmierung

Rekursion kommt in der Mathematik schon lange vor dem Programmieren vor. Sie ist eine Methode, Funktionen, Folgen und Mengen durch Verweis auf kleinere Fälle zu definieren. Induktion wird dann oft verwendet, um Aussagen über diese rekursiven Definitionen zu beweisen.

Wann Rekursion nützlich ist

Rekursion ist nützlich, wenn ein Problem sich natürlich in kleinere Versionen seiner selbst zerlegen lässt. Man sieht sie bei Fakultäten, Fibonacci-artigen Folgen, rekursiv definierten Mengen und vielen Algorithmen.

Sie ist besonders hilfreich, wenn der kleinere Fall dieselbe Struktur wie der ursprüngliche hat. Wenn der kleinere Fall nicht wirklich dieselbe Art von Problem ist, ist Rekursion meist nicht das richtige Werkzeug.

Ein schneller Test für eine saubere rekursive Definition

Stelle zwei Fragen:

1. Habe ich einen Basisfall?
2. Führt jeder rekursive Schritt näher an ihn heran?

Wenn eine der Antworten nein ist, muss die Definition verbessert werden.

Probiere eine ähnliche Aufgabe

Definiere eine Folge durch

$$a_1 = 2, \qquad a_n = a_{n-1} + 3 \quad \text{for } n \ge 2$$

Bestimme dann $a_2$, $a_3$ und $a_4$. Das ist eine schnelle Übung, um in einem neuen Kontext den Basisfall und den rekursiven Schritt zu erkennen.