Was ist Rekursion?

Rekursion ist der Prozess, bei dem eine Funktion sich selbst aufruft. In der Programmierung ist eine rekursive Funktion eine Funktion, die sich direkt oder indirekt selbst aufruft. Um eine Endlosschleife zu vermeiden, muss eine rekursive Funktion einen Basissatz (Basisfall) haben, bei dem sie aufhört, sich selbst aufzurufen.

Anwendungsbeispiele:

• Durchlauf durch Datenstrukturen (z.B. Bäume).
• Lösung von Problemen, die in kleinere Unteraufgaben derselben Art zerlegt werden können (z.B. Berechnung der Fakultät).

Beispiel für die Berechnung der Fakultät mit Rekursion:

def factorial(n):
  # Basisfall: Fakultät von 0 ist 1
  if n == 0:
    return 1
  # Rekursiver Fall: Fakultät von n = n * Fakultät von (n-1)
  else:
    return n * factorial(n - 1)

# Beispielanwendung
result = factorial(5)
# result wird 120 sein

Nachteile der Rekursion:

• Kann viel Speicher durch den Aufruf-Stack verbrauchen.
• Kann weniger effizient sein im Vergleich zu iterativen Lösungen für manche Probleme.
• Kann zu Stapelüberläufen bei tiefen rekursiven Aufrufen führen.