Rekursion in

Über Rekursion

Rekursion ist eine Möglichkeit, Code innerhalb einer Funktion wiederholt auszuführen, indem die Funktion sich selbst aufruft. Funktionen, die sich selbst aufrufen, nennt man rekursive Funktionen. Rekursion kann als eine weitere Möglichkeit angesehen werden, zu schleifen oder zu iterieren. Und wie beim Schleifen wird ein boolescher Ausdruck oder ein True/False-Test verwendet, um zu bestimmen, wann die rekursive Ausführung beendet werden soll.

Anders als beim Schleifen kann eine Rekursion ohne Abbruch in Python nicht unendlich oft ausgeführt werden. Die bei jedem Funktionsaufruf verwendeten Werte werden in einem eigenen Frame auf dem Stack des Python-Interpreters abgelegt. Wenn die Gesamtzahl der Funktionsaufrufe mehr Platz beansprucht, als der Stack bietet, führt dies zu einem Fehler.

Schleifen vs. rekursive Implementierung

Schleifen und Rekursion mögen sich ähnlich anfühlen, da beide iterativ sind. Allerdings sehen sie unterschiedlich aus, sowohl auf Codeebene als auch auf Implementierungsebene. Schleifen können innerhalb desselben Frames auf dem Aufrufstapel stattfinden. Dies wird normalerweise durch Aktualisieren eines oder mehrerer Variablenwerte verwaltet, um den Zustand für jede Iteration fortlaufend zu pflegen. Dies ist eine effiziente Implementierung, aber der Code kann beim Betrachten etwas unübersichtlich wirken.

Rekursion kann, anstatt den Variablenzustand zu aktualisieren, aktualisierte Werte direkt als Argumente an den nächsten Aufruf (Iteration) derselben Funktion übergeben. Das macht den Funktionskörper übersichtlicher und kann verdeutlichen, wie jede Aktualisierung erfolgt. Allerdings ist sie auch eine weniger effiziente Implementierung, da jeder Aufruf derselben Funktion einen weiteren Frame zum Stack hinzufügt.

Rekursion: Warum und warum nicht?

Wenn die Gefahr besteht, einen Stackfehler oder -überlauf zu verursachen, warum sollte dann jemand eine rekursive Strategie zur Lösung eines Problems verwenden? Lesbarkeit, Nachvollziehbarkeit und Absicht. Es kann Situationen geben, in denen eine Lösung lesbarer und/oder leichter nachvollziehbar ist, wenn sie durch Rekursion statt durch Schleifen ausgedrückt wird. Es kann auch Programm-Einschränkungen geben, was die Verwendung/Mutation von Daten, das Verwalten von Komplexität, das Delegieren von Verantwortung oder das Organisieren von Arbeitslasten betrifft.

Probleme, die sich für Rekursion eignen, sind komplexe, aber repetitive Probleme, die mit der Zeit kleiner werden, insbesondere Teile-und-herrsche-Algorithmen und kumulative Algorithmen. Aufgrund der Begrenzung von Python, wie viele Frames auf dem Stack erlaubt sind, werden jedoch nicht alle Probleme von einer vollständig rekursiven Strategie profitieren. Probleme, die weniger natürlich für Rekursion geeignet sind, sind solche, die einen stabilen Zustand haben, aber für eine bestimmte Anzahl von Zyklen wiederholt werden müssen, Probleme, die asynchron ausgeführt werden müssen, und Situationen, die eine große Anzahl von Iterationen erfordern.

Schleifen- vs. rekursive Strategie: Indiras Unsicherheit

Indira lässt ihre monatliche Sozialversicherung automatisch am zweiten Mittwoch eines jeden Monats auf ihr Bankkonto einzahlen. Indira ist besorgt darüber, ihr Scheckbuch auszugleichen. Sie befürchtet, Schecks auszustellen, bevor ihr Geld eingezahlt ist. Sie bittet ihre Enkelin Adya, ihr eine Liste mit Daten zu geben, an denen ihr Geld auf dem Konto erscheint.

Adya, die gerade erst lernt, in Python zu programmieren, schreibt ein Programm nach ihren ersten Überlegungen. Sie möchte eine list der Einzahlungstermine zurückgeben, damit sie ausgegeben werden können. Sie möchte eine Funktion schreiben, die für jedes Jahr funktioniert. Für den Fall, dass sich der Zeitplan ändert (oder dass andere Verwandte möchten, dass Adya ihre Einzahlungspläne berechnet), beschließt sie, dass die Funktion einen zusätzlichen Parameter für den Wochentag benötigt. Schließlich beschließt Adya, dass die Funktion einen Parameter dafür braucht, welcher Wochentag des Monats es ist: der erste, zweite usw. Für all diese Anforderungen beschließt sie, die aus datetime importierte date-Klasse zu verwenden. All das zusammengenommen führt bei Adya zu:

from datetime import date


def paydates_for_year(year, weekday, ordinal):
    """Returns a list of the matching weekday dates.
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    output = []

    for month in range(1, 13):
        for day_num in range(1, 8):
            if date(year, month, day_num).isoweekday() == weekday:
                output.append(date(year, month, day_num + (ordinal - 1) * 7))
                break
    return output

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year(2022, 3, 2))

Diese erste Iteration funktioniert, aber Adya überlegt, ob sie den Code so umgestalten kann, dass er weniger Zeilen und weniger verschachtelte Schleifen verwendet. Sie hat auch gelesen, dass es gut ist, den mutierenden Zustand zu minimieren, also möchte sie sehen, ob sie die Mutation einiger ihrer Variablen wie output, month und day_num vermeiden kann.

Sie kennt sich auch mit Rekursion aus und überlegt, wie sie ihr Programm ändern könnte, um einen rekursiven Ansatz zu verwenden. Die Variablen, die in ihrer Schleifenfunktion erstellt und mutiert werden, könnten stattdessen als Argumente übergeben werden. Anstatt die Variablen innerhalb ihrer Funktion zu mutieren, könnte sie aktualisierte Werte als Argumente an den nächsten Funktionsaufruf übergeben. Mit diesen Absichten gelangt sie zu diesem rekursiven Ansatz:

from datetime import date


def paydates_for_year_rec(year, weekday, ordinal, month, day_num, output):
    """Returns a list of the matching weekday dates
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
        month (int): The month number currently being processed.
        day_num (int): The day number of the month currently being processed.
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    if month == 13:
        return output
        
    if date(year, month, day_num).isoweekday() == weekday:
        return paydates_for_year_rec(
                 year, weekday, ordinal, month + 1, 1, output
                 + [date(year, month, day_num + (ordinal - 1) * 7)]
                 )
    
    return paydates_for_year_rec(year, weekday, ordinal, month, day_num + 1, output)

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year_rec(2022, 3, 2, 1, 1, []))

Adya ist froh, dass es keine verschachtelten Schleifen mehr gibt, keinen mutierten Zustand und 2 Zeilen weniger Code!

Sie ist ein wenig besorgt, dass der rekursive Ansatz mehr Schritte als der Schleifenansatz verwendet und daher weniger „performant“ ist. Aber das Umschreiben des Problems mit Rekursion hat ihr definitiv geholfen, mit unschönen verschachtelten Schleifen (einem Performance-Risiko), umfangreicher Zustandsmutation und Verwirrung um komplexe bedingte Logik umzugehen. Es fühlt sich auch „lesbarer“ an. Sie ist sicher, dass sie, wenn sie nach einer Pause zu diesem Code zurückkehrt, ihn leichter durchlesen und sich merken kann, was er tut.

In Zukunft wird Adya vielleicht versuchen, Probleme zuerst rekursiv zu bearbeiten. Sie könnte es einfacher finden, das Problem zunächst in klaren Schritten durchzugehen, wenn Verschachtelung, Mutation und Komplexität minimiert werden. Nachdem sie die grundlegende Logik ausgearbeitet hat, kann sie sich darauf konzentrieren, ihre anfänglichen rekursiven Schritte zu einem leistungsfähigeren Schleifenansatz zu optimieren.

Noch später, wenn sie etwas über tuples lernt, könnte Adya weitere „optimierende“ Ansätze in Betracht ziehen, wie die Verwendung einer list comprehension mit Calendar.itermonthdates oder das Memoisieren bestimmter Werte.

Rekursive Variante: Der Tail Call

Ein Tail Call liegt vor, wenn die letzte Anweisung einer Funktion nur sich selbst aufruft und nichts weiter. Dieses Beispiel ist kein Tail Call, da die Funktion 1 zum Ergebnis des Selbstaufrufs addiert:

def print_increment(step, max_value):
    if step > max_value:
        return 1
    print(f'The step is {step}')
    return 1 + print_increment(step + 1, max_value)


def main():
    retval = print_increment(1, 2)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

Dies gibt aus:

The step is 1
The step is 2
retval is 3 after recursion

Um es zu einem Tail Call umzugestalten, mache retval zu einem Parameter von print_increment.

def print_increment(step, max_value, retval):
    if step > max_value:
        return retval
    print(f'The step is {step}')
    return print_increment(step + 1, max_value, retval + 1)


def main():
    retval = print_increment(1, 2, 1)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

Du könntest einen Tail Call sogar noch leichter nachvollziehbar finden als einen rekursiven Aufruf, der kein Tail Call ist. Wie auch immer, es ist immer wichtig, bei der Verwendung von Rekursion zu wissen, dass es nicht so viele Iterationen geben wird, dass der Stack überläuft.

Rekursionsgrenzen in Python

Einige Sprachen sind in der Lage, Tail Calls zu optimieren, sodass jeder rekursive Aufruf den Stackframe des ersten Aufrufs der Funktion wiederverwendet (ähnlich wie eine Schleife einen Frame wiederverwendet), anstatt einen zusätzlichen Frame zum Stack hinzuzufügen. Python gehört nicht zu diesen Sprachen. Um sich vor einem Stacküberlauf zu schützen, hat Python eine Rekursionsgrenze, die standardmäßig eintausend Frames beträgt. Eine RecursionError-Ausnahme wird ausgelöst, wenn der Interpreter erkennt, dass die Rekursionsgrenze überschritten wurde. Es ist möglich, die Methode sys.setrecursionlimit zu verwenden, um die Rekursionsgrenze zu erhöhen, aber dies birgt das Risiko eines Laufzeit-Segmentierungsfehlers, der das Programm und möglicherweise das Betriebssystem zum Absturz bringt.

Ressourcen

Um mehr über die Verwendung von Rekursion in Python zu erfahren, kannst du mit Folgendem beginnen:

• python-programming: recursion
• Real Python: python-recursion
• Real Python: python-thinking-recursively