Level 7: Um Rekursion zu verstehen, musst du erst Rekursion verstehen #

Ein Beispiel, das deinen Rechner eine Weile beschäftigen wird #

Du weißt bereits, dass du oft benötigte Dinge in Funktionen schreiben kannst. Diese Funktionen kannst du dann immer wieder aufrufen, und sparst dir so viele Zeilen Code. (Außerdem werden eventuelle Änderungen einfacher, weil du sie nur einmal vornehmen musst und keine Stelle im Code übersehen kannst.)

Wußtest du aber auch, dass eine Funktion sich selbst aufrufen kann? Das mag erst einmal unsinnig klingen (und ist es manchmal auch), doch lassen sich – richtig gemacht – sehr elegant Lösungen für viele (manche würden sagen: für alle!) Programmierprobleme finden.

Übernimm einmal folgenden Code nach Thonny und lies ihn dir durch. sleep(3) legt den Thread, in dem dein Programm läuft, für drei Sekunden schlafen – den Rest solltest du verstehen. Vielleicht musst du dein Konsolenfenster etwas größer machen, bevor du das Programm startest. (Wenn du mitsingen möchtest: das Lied lässt sich auf die Melodie von »Mein Hut, der hat drei Ecken« singen.) Überprüfe nun, ob du mit deinen Vermutungen richtig lagst, indem du das Programm ausführst!

from time import sleep

def singe():
    print('Ein Mops kam in die Küche, '
          + 'und stahl dem Koch ein Ei,\n'
          + 'da nahm der Koch den Löffel, '
          + 'und schlug den Mops entzwei.\n\n'
          + 'Da kamen viele Möpse, '
          + 'und gruben ihm ein Grab\n'
          + 'und setzten ihm ’nen Grabstein, '
          + 'auf dem geschrieben stand:\n\n'
          )
    sleep(3)
    singe()

singe()

Lagst du richtig? Ähnlich einer while True:-Wiederholung hört der Rechner nicht auf, das Mops-Lied zu singen. (Oder genauer: er hört erst auf, wenn ihm der Speicher ausgeht. Aber bis dahin versucht er es!)

Wenn eine Funktion sich selbst aufruft, so nennen Programmierer:innen das Rekursion, und den Aufruf einer Funktion aus sich selbst heraus einen rekursiven Funktionsaufruf. Und auch, wenn es auf den ersten Blick nicht so scheint: mit Rekursionen lässt sich alles berechnen, was berechnet werden kann.

Buchstaben zählen #

Damit du Rekursion noch sinnvoller einsetzen kannst, hier ein einfaches Beispiel mit echtem Nutzen. Angenommen, du möchtest die Länge einer Zeichenkette bestimmen, so kannst du dieses Problem auch rekursiv lösen. (Du kennst die Funktion len… die werden wir der größeren Freude wegen nicht verwenden!)

Beginne mit den einfachen Problemen #

Sehr oft ist es eine gute Idee, ein Problem in kleinere Teile zu zerlegen. Sind alle kleinen Probleme gelöst, lässt sich auch das größere lösen.

Bei einer Zeichenkette, die leer ist, ist die Länge ziemlich offensichtlich 0. Einen solchen Fall nennen wir Basisfall. Der Basisfall ist eigentlich immer die offensichtliche Lösung des kleinsten Teilproblems, und wir können sie einfach hinschreiben.

So auch hier:

def laenge(zeichenkette):
    if not zeichenkette:
        return 0

And again: Truthiness!

Eine leere Zeichenkette, die wir nach ihrem Wahrheitswert (True oder False) befragen, wird zu False ausgewertet. Mit not drehen wir das Ergebnis der Auswertung zu True um, und geben 0 zurück. Das war einfach! (Dass man Zeichenketten auf diese Art nach ihrem Wahrheitswert befragen kann, ist übrigens eine Python-Besonderheit – die uns aber oft Wege abkürzen lässt!)

Was aber, wenn die Zeichenkette nicht leer ist? Wie kommen wir dann auf die Länge?

Irgendwann sollten wir bei unserem Basisfall ankommen, und dazu können wir nach und nach Zeichen entfernen. (Wir müssen uns nur merken, wieviele Zeichen das waren…) Genau das kannst du im Rekursionsfall festlegen. Den fügen wir nach einem else hinzu:

def laenge(zeichenkette):
    if not zeichenkette:
        # Das ist unser Basisfall…
        return 0  
    else:
        # …und das unser Rekursionsfall!
        return 1 + laenge(zeichenkette[1:])

Teste nun deine erste rekursive Funktion! Wenn Du Thonny benutzt, füge doch die Zeile

print(laenge('Hallo'))

hinzu, und nutze den Debug-Modus (Klick auf den Käfer!). Beim wiederholten Druck der Taste F7 solltest du jetzt sehen können, wie deine Funktion sich wieder und wieder selbst aufruft. Dabei wird die Zeichenkette immer kürzer: nach »Hallo« kommt »allo«, dann »llo« und so weiter. Erst wenn der Basisfall erreicht ist (eine leere Zeichenkette), werden die Ergebnisse nach und nach zusammengetragen, und der Stapel von (rekursiven) Funktionsaufrufen abgebaut.

Übung: Der rekursive Palindrom-Checker #

Es wird Zeit, deine neu erworbenen Kenntnisse einzusetzen! Außerdem kannst du für diese Übung unsere selbst geschriebene Funktion laenge gut gebrauchen!

Übernimm den folgenden Code in deine IDE. Für einen funktionierenden Palindrom-Checker fehlt noch genau eine Zeile!

(Um die Sache erst einmal auf das Wesentliche zu beschränken, kümmern wir uns nicht um Leerzeichen oder Großbuchstaben.)

import doctest

def laenge(zeichenkette):
    if not zeichenkette:
        # Das ist unser Basisfall…
        return 0  
    else:
        # …und das unser Rekursionsfall!
        return 1 + laenge(zeichenkette[1:])

def ist_palindrom(wort):
    """
    Diese Funktion gibt für Zeichenketten, die
    nur Kleinbuchstaben enthalten, einen Wahrheits
    wert zurück, der anzeigt, ob die Zeichenkette
    ein Palindrom ist.
    
    >>> ist_palindrom('anna')
    True
    >>> ist_palindrom('uhu')
    True
    >>> ist_palindrom('tomate')
    False
    """
    if laenge(wort) < 2:
        return True
    else:
        pass # Ersetze diese Zeile durch den Rekursionsfall
        
if __name__ == '__main__':
    doctest.testmod()
    print(ist_palindrom('uhu'))

Was ist Zeit?

Wenn ich an dieser Stelle eine persönliche Erfahrung teilen darf: wenn ich rekursive Funktionen schreibe, verbringe ich manchmal längere Zeit damit, zu überlegen, wie die Rekursion arbeitet. Nach absurd langer Zeit stehen zwei bis vier Zeilen Code in meiner Datei, die – trotz oder wegen ihrer Kürze – genau das tun, was sie sollen.

Sollte es einmal länger dauern, gräme dich nicht! Nimm dir die Zeit, und erfreue dich nach getaner Arbeit am Debug-Modus, in dem du einmal rekursive Stapel erklimmst und wieder herabsteigst!

import doctest

def laenge(zeichenkette):
    if not zeichenkette:
        # Das ist unser Basisfall…
        return 0  
    else:
        # …und das unser Rekursionsfall!
        return 1 + laenge(zeichenkette[1:])

def ist_palindrom(wort):
    """
    Diese Funktion gibt für Zeichenketten, die
    nur Kleinbuchstaben enthalten, einen Wahrheits
    wert zurück, der anzeigt, ob die Zeichenkette
    ein Palindrom ist.
    
    >>> ist_palindrom('anna')
    True
    >>> ist_palindrom('uhu')
    True
    >>> ist_palindrom('tomate')
    False
    """
    if laenge(wort) < 2:
        return True
    else:
        return wort[0] == wort[-1] and ist_palindrom(wort[1:-1])
    
if __name__ == '__main__':
    doctest.testmod()
    print(ist_palindrom('uhu'))

Zurück Weiter