Vorlesungsskript 19

Rekursion

Eine Funktion ist rekursiv, wenn sie sich selbst aufruft, wenn also in ihrem Körper ein Aufruf derselben Funktion vorkommt. Ein einfaches Beispiel:

def f():
    '''Returns the result of calling itself.'''
    return f()

Diese Funktion hat keine Argumente. Auch macht sie offensichtlich keinen Sinn. Um ihren Rückgabewert zu bestimmen, ruft sie sich selbst mit denselben Argumenten (keinen) auf. Sie ist also zirkulär definiert. Beim Versuch, den Funktionsaufruf f() auszuwerten, würde das zu einer Endlosschleife führen, wenn der Python-Interpreter nicht nach einer gewissen Anzahl rekursiver Aufrufe aufgeben würde:

>>> f()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in f
  File "<stdin>", line 2, in f
  File "<stdin>", line 2, in f
  [Previous line repeated 995 more times]
RecursionError: maximum recursion depth exceeded

Und dennoch können rekursive Funktionen nützlich sein. Nämlich immer dann, wenn man, um ein Problem zu lösen, zunächst eine kleinere Version desselben Problems lösen muss. Und um diese kleinere Version zu lösen, wiederum eine noch kleinere Version. Bis man irgendwann bei einem so kleinen Problem landet, dem sogenannten Rekursionsanfang, dass man es ohne einen weiteren rekursiven Aufruf lösen kann.

Ein klassisches Beispiel aus der Mathematik ist die Berechnung der Fakultät einer nichtnegativen ganzen Zahl n, geschrieben n!. Zum Beispiel ist 4! = 4⋅3⋅2⋅1, 10! = 10⋅9⋅8⋅7⋅6⋅5⋅4⋅3⋅2⋅1, etc. Die allgemeine Definition der Fakultät n! unterscheidet zwei Fälle: Entweder ist n=0. Dann gilt: n!=1. Das ist der Rekursionsanfang. Oder n ist eine positive ganze Zahl. Dann gilt: n!=n⋅(n-1)!, die Fakultät von n ist also das Produkt von n und der Fakultät von n-1. Dieser zweite Fall ist der Rekursionsschritt. Um die Fakultät einer positiven Ganzzahl zu berechnen, muss man also zunächst die Fakultät der nächstkleineren Ganzzahl kennen. Das ist aber kein Problem, denn wenn man so rechnet, kommt man irgendwann bei 0! raus, dem Rekursionsanfang. Dieser lässt sich ohne weiteren Rekursionsschritt lösen.

Eine Python-Funktion zur Berechnung der Fakultät könnte also so aussehen:

def fac(n):
    '''Returns the factorial of the nonnegative integer n.'''
    if n == 0:
        return 1
    else:
	return n * fac(n - 1)

Die Unterscheidung zwischen Rekursionsanfang und Rekursionsschritt ist mit Hilfe einer Verzweigung umgesetzt. Es kommt nicht zu einer Endlosschleife, da die Funktion jedes Mal mit einem anderen Argument aufgerufen wird und schließlich der Rekursionsanfang (n == 0) erreicht wird.

Rekursive Datenstrukturen

Einer der wichtigen Einsatzzwecke für Rekursion ist das Verarbeiten von rekursiven Datenstrukturen. Eine rekursive Datenstruktur ist eine Datenstruktur, die wiederum Datenstrukturen desselben Typs enthalten kann. Python-Listen sind zum Beispiel rekursive Datenstrukturen, da sie wiederum Python-Listen enthalten können. Zum Beispiel:

[2, [3, 4, [5, 6]], [7, 8]]

In dieser Liste sind wiederum Listen verschachtelt, und darin wiederum Listen. Im Prinzip könnte diese Verschachtelung bis zu einer beliebigen Tiefe weitergehen. (Für die Computerlinguistik ist das u.a. für die automatische Analyse von Schachtelsätzen interessant, aber bleiben wir für den Moment bei dem abstrakten Beispiel.) Wie finden wir z.B. heraus, ob die Zahl 5 irgendwo als ein verschachteltes Element der Liste vorkommt? Der in-Operator macht das nicht, der guckt nur die direkten Elemente der Liste an:

>>> 5 in [2, [3, 4, [5, 6]], [7, 8]]
False

Die Lösung ist eine rekursive Funktion – nennen wir sie deep_in –, die das gesuchte Objekt nicht nur bei den Elementen der Liste sucht, sondern auch bei den Elemente der Elemente, den Elementen der Elemente der Elemente usw. deep_in wird mit zwei Argumenten aufgerufen: dem gesuchten Objekt x und dem durchsuchten Objekt l:

def deep_in(x, l):
    '''Returns whether x occurs in l.

    x "occurs" in l if x and l are equal or l is a list and x "occurs" in one
    of l's elements.'''
    if x == l:
        return True
    if isinstance(l, list):
        for e in l:
            if deep_in(x, e):
                return True
    return False

Sind x und l gleich, gibt die Funktion direkt True zurück. Das ist der Rekursionsanfang. Andernfalls, falls l eine Liste ist, werden seine Elemente entsprechend durchsucht. Das ist der Rekursionsschritt. Ist die Suche erfolgreich, wird True zurückgegeben. Andernfalls wird False zurückgegeben.

Zum Beispiel:

>>> deep_in(1, [2, [3, 4, [5, 6]], [7, 8]])
False
>>> deep_in(2, [2, [3, 4, [5, 6]], [7, 8]])
True
>>> deep_in(3, [2, [3, 4, [5, 6]], [7, 8]])
True
>>> deep_in(4, [2, [3, 4, [5, 6]], [7, 8]])
True
>>> deep_in(5, [2, [3, 4, [5, 6]], [7, 8]])
True
>>> deep_in(6, [2, [3, 4, [5, 6]], [7, 8]])
True
>>> deep_in(7, [2, [3, 4, [5, 6]], [7, 8]])
True
>>> deep_in(8, [2, [3, 4, [5, 6]], [7, 8]])
True
>>> deep_in(9, [2, [3, 4, [5, 6]], [7, 8]])
False