Level 7: Eine Rekursionsvariable #

Wie viel darf es denn sein? #

Bisher haben sich unsere Basisfälle ganz natürlich ergeben. Entweder war die Zeichenkette zu Ende, oder die Länge war 1, oder das nächste Zeichen sollte nicht mehr mitgezählt werden, weil es anders war. Wie sieht es nun aus, wenn wir die Folge nach und nach ausgeben wollen?

Naheliegend ist eine rekursive Lösung, die ein wenig dem Lied von dem Mops und dem Koch gleicht:

def unendliche_folge_von_look_and_say(wort):
    naechstes_startwort = look_and_say(wort)
    print(naechstes_startwort)
    unendliche_folge_von_look_and_say(naechstes_startwort)

Was meinst du, wird hier passieren? Überlege zuerst, und probier’ dann aus, ob Du richtig lagst. (Füge die Funktion unendliche_folge_von_look_and_say so wie oben zu sehen in deine Datei mit den anderen rekursiven Funktionen ein, führe das Programm einmal in Thonny aus und starte dann die Funktion im REPL:

>>> unendliche_folge_von_look_and_say('1')

Zunächst sollten eine Menge neue Elemente der Folge ausgegeben werden – das ist gut! Doch halt, was passiert dann? Eine Fehlermeldung!

RecursionError: maximum recursion depth exceeded

Die Laufzeitumgebung (sie führt deine Python-Programme aus) gibt eine Höchstzahl an Rekursionen vor – das ist die Rekursionstiefe. Diese Zahl ist begrenzt, um unkontrollierte Abstürze zu vermeiden. All die rekursiven Aufrufe bleiben ja im Hauptspeicher, bis der Stapel an Rekursionen wieder abgebaut wird (wenn der Basisfall erreicht wird). Bei einer unendlichen Rekursion würde der Speicher irgendwann volllaufen, und das wird mit der Vorgabe der Rekursionstiefe verhindert. Das ist in den meisten Fällen auch ganz sinnvoll…

Um nun trotzdem mehrere Elemente unserer gewünschten Folge auszugeben, bestimmen wir schon im Voraus die Anzahl von Elementen, die wir uns wünschen. Dies kannst du mit einer künstlichen Rekursionsvariablen erledigen: sie bestimmt den Basisfall, und wird mit jedem rekursiven Aufruf um eins vermindert. So kannst du sicherstellen, dass die rekursiven Aufrufe irgendwann aufhören. (Hier wird nach und nach ein String zusammengesetzt. \n ist der Zeilenumbruch, schließlich wird die geforderte Anzahl von Elementen der Folge zusammen zurückgegeben, las steht für »look and say«.)

def las_folge(anzahl, wort):
    naechstes = look_and_say(wort)
    # Basisfall: bei 0 machen wir nicht weiter
    if anzahl < 1: 
        return ''
    # Rekursionsfall: Das was geschehen soll, geschieht einmal,
    # dann wird die Funktion mit verminderter Anzahl wieder
    # aufgerufen.
    else:
        return naechstes + '\n' + las_folge(anzahl-1, naechstes)

Test auch diese Funktion, und probiere, wie tief dein Rechner hinabsteigen kann!

Look-and-say rekursiv #

Nun hast du schon eine Ahnung davon, was Rekursion bedeutet. Rekursive Lösungen zu Problemen sind zwar nicht immer die schnellsten, doch wenn du einmal verstanden hast, wie sie funktioniert, lassen sich viele Probleme einfach und elegant damit lösen.

Hier nochmal all unsere rekursiven Funktionen in ganzer Schönheit:

def laenge(zeichenkette):
    if not zeichenkette:
        return 0
    else:
        return 1 + laenge(zeichenkette[1:])

def zaehle_gleiche_hintereinander(wort):
    laenge_wort = laenge(wort)
    if laenge_wort < 1:
        return 0
    elif laenge_wort < 2:
        return 1
    elif wort[0] != wort[1]:
        return 1
    else:
        return 1 + zaehle_gleiche_hintereinander(wort[1:])

def look_and_say(wort):
    if laenge(wort) < 1:
        return ''
    else:
        gleich = zaehle_gleiche_hintereinander(wort)
        return str(gleich) + wort[0] + look_and_say(wort[gleich:])

def unendliche_folge_von_look_and_say(wort):
    naechstes_startwort = look_and_say(wort)
    print(naechstes_startwort)
    unendliche_folge_von_look_and_say(naechstes_startwort)

def las_folge(anzahl, wort):
    naechstes = look_and_say(wort)
    if anzahl < 1:
        return ''
    else:
        return naechstes + '\n' + las_folge(anzahl-1, naechstes)

# Damit etwas passiert, lassen wir uns die ersten zehn
# Elemente einer look-and-say-Folge ausgeben:
print(las_folge(10,'1'))

Wenn du tiefergehendes Interesse an Rekursion hast, und dich für Probleme interessierst, die sich damit gut bearbeiten lassen (wie z.B. das finden von Wegen in Labyrinthen), möchte ich dir das Recursive Book of Recursion von Al Sweigart empfehlen.

Zurück Weiter