Rekursion

Rekursion ist eine Methode, bei der etwas durch Bezugnahme auf sich selbst definiert wird. In der Mathematik bedeutet dies, dass ein neues Glied in einer Folge, einer Funktion oder einer Menge von früheren Schritten abhängt. Auf diese Weise können komplexe Strukturen aus einem einfachen Anfang aufgebaut werden.

 

Ein einfaches Beispiel ist eine rekursiv definierte Folge:

 

$$ \large a_{n} = 2 \cdot a_{n-1}, \quad a_{0} = 1 $$

 

Der Startpunkt ist \( \large a_{0} = 1 \). Jedes neue Glied erhält man, indem man das vorherige mit 2 multipliziert. Damit sind die ersten Werte

 

$$ \large a_{1} = 2, \quad a_{2} = 4, \quad a_{3} = 8, \quad a_{4} = 16, \ldots $$

 

Rekursive und explizite Form

Eine rekursive Formel beschreibt ein Glied aus den vorherigen. Oft kann man auch eine explizite Formel finden, bei der jedes Glied direkt berechnet wird, ohne die vorherigen zu kennen. Für das obige Beispiel gilt

 

$$ \large a_{n} = 2^n $$

 

Rekursive Definitionen zeigen gut die Struktur, während explizite Formeln schnell für Berechnungen sind. Beide Ansätze sind nützlich und eng miteinander verbunden.

 

Folgen

Rekursion wird verwendet, um viele bekannte Folgen zu definieren. Zum Beispiel die Fibonacci-Folge, bei der jedes Glied die Summe der beiden vorhergehenden ist.

 

$$ \large F_{n} = F_{n-1} + F_{n-2}, \quad F_{0} = 0, \quad F_{1} = 1 $$

 

Funktionen

Ein weiteres Beispiel ist die Fakultätsfunktion. Sie kann rekursiv definiert werden als

 

$$ \large n! = n \cdot (n-1)!, \quad 0! = 1 $$

 

Mengen

Auch Mengen können rekursiv definiert werden. Wenn man damit beginnt, dass 3 zur Menge gehört, und dann jeweils 3 addiert, erhält man alle durch 3 teilbaren Zahlen. Dies lässt sich als rekursive Definition schreiben:

 

$$ \large 3 \in M, \quad x \in M \;\Rightarrow\; x + 3 \in M $$

 

Pascalsches Dreieck

Ein bekanntes geometrisches Beispiel ist das Pascalsche Dreieck. Jede Zahl entsteht rekursiv als Summe der beiden Zahlen darüber. Dies ergibt eine dreieckige Struktur, die die Binomialkoeffizienten enthält.

 

$$ \large
\begin{array}{cccccccccccccccccc}
        &       &       &       &       &       &       &       & 1     &       &       &       &       &       &       &       \\
        &       &       &       &       &       &       & 1     &       & 1     &       &       &       &       &       &       \\
        &       &       &       &       &       & 1     &       & 2     &       & 1     &       &       &       &       &       \\
        &       &       &       &       & 1     &       & 3     &       & 3     &       & 1     &       &       &       &       \\
        &       &       &       & 1     &       & 4     &       & 6     &       & 4     &       & 1     &       &       &       \\
        &       &       & 1     &       & 5     &       & 10    &       & 10    &       & 5     &       & 1     &       &       \\
        &       & 1     &       & 6     &       & 15    &       & 20    &       & 15    &       & 6     &       & 1     &       \\
        & 1     &       & 7     &       & 21    &       & 35    &       & 35    &       & 21    &       & 7     &       & 1     \\
  1     &       & 8     &       & 28    &       & 56    &       & 70    &       & 56    &       & 28    &       & 8     &       & 1 \\
\end{array}
$$

 

 

Anwendung

Rekursion ist ein grundlegendes Werkzeug der diskreten Mathematik. Sie wird verwendet, um unendliche Prozesse zu beschreiben, Eigenschaften mithilfe der Induktion zu beweisen und Algorithmen zu konstruieren. Auch in der Geometrie spielt Rekursion eine Rolle, zum Beispiel beim Aufbau von Fraktalen.

 

Zusammenhang mit Induktion

Beim Arbeiten mit rekursiven Definitionen ist die Induktion ein natürliches Beweiswerkzeug. Man zeigt zuerst, dass eine Aussage im Basisfall gilt, und anschließend, dass sie von einem Schritt zum nächsten erhalten bleibt. Damit können Eigenschaften für die gesamte unendliche, rekursiv definierte Struktur bewiesen werden.