Rekursion

Rekursion ist eine wichtige Programmiertechnik, das auf dem gleichnamigen mathematischen Konstrukt basiert. Im Zentrum der Rekursion stehen zwei Konzepte:

1. Abbruchbedingung
2. Selbstaufruf

Eine rekursive Funktion ruft sich so lange selbst auf, bis eine bestimmte Abbruchbedingung erfüllt ist. Wenn diese Bedingung erfüllt ist, kommt der Programmablauf zum Ende. Darum ist die Abbruchbedingung so wichtig, denn ohne sie würde das Programm ewig weiterlaufen und sich immer wieder selbst aufrufen.

💬

Beispiel

Die Fibonacci-Zahlenfolge ist rekursiv definiert als

${\begin{aligned}F_{0}&=0\\F_{1}&=1\\F_{n}&=F_{n-1}+F_{n-2}\\\end{aligned}}$

$F_{4}$ berechnet sich dann wie folgt:

${\begin{aligned}F_{4}&=F_{3}+F_{2}\\&=(F_{2}+F_{1})+(F_{1}+F_{0})\\&=((F_{1}+F_{0})+F_{1})+(F_{1}+F_{0})\\&=((1+0)+1)+(1+0)\\&=3\end{aligned}}$

In Python könnte man dies wie folgt implementieren:

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1:
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Manche Algorithmen wie Quicksort oder Mergesort sind per se schon rekursiv definiert, sodass es sinnvoll ist, sie auch rekursiv zu programmieren. Manche Programmierys finden rekursive Programme leichter lesbar als iterativ programmierte, die auf Kontrollstrukturen wie bedingten Wiederholungen beruhen.

Häufig sind rekursiv programmierte Funktionen kompakter als iterative, weil in iterativen Programmen oft zusätzliche Variablen wie Akkumulatoren und Laufvariablen definiert werden müssen. Dafür sind iterative Programme oft schneller in der Ausführung und benötigen weniger Arbeitsspeicher, weil bei jedem Aufruf einer Funktion Daten dort abgelegt werden müssen.

Da es bei rekursiver Programmierung leichter ist, ohne Seiteneffekte zu programmieren, ist es auch leichter, die Korrektheit von rekursiven Programmen zu beweisen. Manche Programmiersprachen wie LISP oder Haskell bringen von sich aus überhaupt keine iterativen Strukturen mit und erlauben nur rekursive Programmierung.

Weblinks

• "Rekursive Algorithmen" auf inf-schule.de 🇩🇪