Rekursive Funktionen

In der Mathematik ist die Verwendung von Rekursion zur Definition von Funktionen Gang und Gäbe. Eine typische Definition der Fakultätsfunktion sieht zum Beispiel so aus.

Image

Diese Definition können wir mit Hilfe einer bedingten Verzweigung direkt nach Python übersetzen:

def factorial(n):
  if n == 1:
    return 1
  else:
    return n * factorial(n-1)

Falls der Parameter n gleich 1 ist, ist das Ergebnis ebenfalls 1. Falls nicht, wird das Ergebnis mit Hilfe eines rekursiven Aufrufs berechnet.

Rekursive Funktionen sind oft auf diese Weise strukturiert. Mit einer bedingten Verzweigung wird die Abbruchbedingung geprüft, die darüber entscheidet, ob die Berechnung beendet wird oder weiter geht. Im Fall, dass die Berechnung weiter geht, folgt ein rekursiver Aufruf, im Abbruchfall nicht. Falls die Abbruchbedingung nie erfüllt ist, terminiert die Berechnung nicht, genau wie bei einer bedingten Wiederholung, deren Bedingung immer erfüllt ist.

Programmtabellen sind nicht geeignet um die Auswertung rekursiver Funktionen zu veranschaulichen, da deren Parameter-Variablen für jeden Aufruf unterschiedliche Werte haben können. Unterschiedliche Variablen mit dem selben Namen in einer Tabelle zu verwalten wird schnell unübersichtlich.

Statt mit einer Programmtabelle können wir die Auswertung rekursiver Funktionen wie hier am Beispiel der Fakultätsfunktion demonstriert veranschaulichen.

factorial(4):
Die Abbruchbedingung ist nicht erfüllt
Das Ergebnis von factorial(4) ist 4 * factorial(3)
Es muss zuerst factorial(3) ausgewertet werden.
  factorial(3):
  Die Abbruchbedingung ist nicht erfüllt
  Das Ergebnis von factorial(3) ist 3 * factorial(2)
  Es muss zuerst factorial(2) ausgewertet werden.
    factorial(2):
    Die Abbruchbedingung ist nicht erfüllt
    Das Ergebnis von factorial(2) ist 2 * factorial(1)
    Es muss zuerst factorial(1) ausgewertet werden.
      factorial(1):
      Die Abbruchbedingung ist erfüllt
      Das Ergebnis von factorial(1) ist 1.
    Das Ergebnis von factorial(2) ist also 2 * 1 = 2.
  Das Ergebnis von factorial(3) ist also 3 * 2 = 6.
Das Ergebnis von factorial(4) ist also 4 * 6 = 24.

Statt einer Funktion, die sich selbst aufruft, können wir auch Gruppen mehrerer rekursiver Funktionen definieren, die sich gegenseitig aufrufen. Die folgenden Definitionen illustrieren diese Technik:

def is_even(n):
  if n == 0:
    return True
  else:
    return is_odd(n-1)
  
def is_odd(n):
  if n == 0:
    return False
  else:
    return is_even(n-1)

Die Funktion is_even() liefert True oder False zurück, je nachdem ob die gegebene Zahl n gerade ist oder nicht. Sie verwendet dazu im rekursiven Fall die Funktion is_odd(), die ihrerseits is_even() im rekursiven Fall verwendet. Die Abbruchbedingung beider Funktionen testet, ob das Argument gleich Null ist. Für negative Eingaben definieren diese Funktionen deshalb nicht, was es heißt, gerade oder ungerade zu sein und ein Aufruf mit einem negativen Argument terminiert nicht.