Grundlagen der Rekursion in Python

Lesezeit: 8 Minuten

Grundlagen der Rekursion in Python
Sebastian S

“Schreiben Sie eine rekursive Funktion, “listSum”, die eine Liste von ganzen Zahlen nimmt und die Summe aller ganzen Zahlen in der Liste zurückgibt.”

Beispiel:

>>> listSum([1, 3, 4, 5, 6])
19

Ich weiß, wie man das anders macht, aber nicht rekursiv.

def listSum(ls):
    i = 0
    s = 0
    while i < len(ls):
        s = s + ls[i]
        i = i + 1
    print(s)

Ich brauche die grundlegende Methode, um dies zu tun, da spezielle eingebaute Funktionen nicht erlaubt sind.

1644076027 833 Grundlagen der Rekursion in Python
das vierte Auge

Wenn Sie auf ein solches Problem stoßen, versuchen Sie, das Ergebnis der Funktion mit derselben Funktion auszudrücken.

In Ihrem Fall können Sie das Ergebnis erhalten, indem Sie die erste Zahl mit dem Ergebnis des Aufrufs derselben Funktion mit den restlichen Elementen in der Liste hinzufügen.

Beispielsweise,

listSum([1, 3, 4, 5, 6]) = 1 + listSum([3, 4, 5, 6])
                         = 1 + (3 + listSum([4, 5, 6]))
                         = 1 + (3 + (4 + listSum([5, 6])))
                         = 1 + (3 + (4 + (5 + listSum([6]))))
                         = 1 + (3 + (4 + (5 + (6 + listSum([])))))

Nun, was sollte das Ergebnis sein listSum([])? Es sollte 0 sein. Das heißt Grundzustand Ihrer Rekursion. Wenn die Grundbedingung erfüllt ist, endet die Rekursion. Versuchen wir nun, es umzusetzen.

Die Hauptsache hier ist, die Liste aufzuteilen. Dazu können Sie Slicing verwenden.

Einfache Version

>>> def listSum(ls):
...     # Base condition
...     if not ls:
...         return 0
...
...     # First element + result of calling `listsum` with rest of the elements
...     return ls[0] + listSum(ls[1:])
>>> 
>>> listSum([1, 3, 4, 5, 6])
19

Tail-Call-Rekursion

Sobald Sie verstehen, wie die obige Rekursion funktioniert, können Sie versuchen, sie ein wenig besser zu machen. Um nun das tatsächliche Ergebnis zu finden, sind wir auch vom Wert der vorherigen Funktion abhängig. Der return -Anweisung kann den Wert nicht sofort zurückgeben, bis der rekursive Aufruf ein Ergebnis zurückgibt. Wir können dies vermeiden, indem wir den Strom wie folgt an den Funktionsparameter übergeben

>>> def listSum(ls, result):
...     if not ls:
...         return result
...     return listSum(ls[1:], result + ls[0])
... 
>>> listSum([1, 3, 4, 5, 6], 0)
19

Hier übergeben wir in den Parametern den Anfangswert der Summe, der Null ist listSum([1, 3, 4, 5, 6], 0). Dann, wenn die Basisbedingung erfüllt ist, akkumulieren wir tatsächlich die Summe in der result Parameter, also geben wir ihn zurück. Nun das letzte return Aussage hat listSum(ls[1:], result + ls[0]), wo wir das erste Element zum Strom hinzufügen result und übergeben Sie es erneut an den rekursiven Aufruf.

Dies könnte ein guter Zeitpunkt sein, um das zu verstehen Rückruf. Es wäre für Python nicht relevant, da es keine Tail-Call-Optimierung durchführt.


Weitergabe der Indexversion

Jetzt denken Sie vielleicht, dass wir so viele Zwischenlisten erstellen. Kann ich das vermeiden?

Natürlich kannst du. Sie benötigen lediglich den Index des als nächstes zu verarbeitenden Elements. Aber jetzt wird der Grundzustand ein anderer sein. Da wir den Index übergeben werden, wie werden wir feststellen, wie die gesamte Liste verarbeitet wurde? Nun, wenn der Index der Länge der Liste entspricht, haben wir alle darin enthaltenen Elemente verarbeitet.

>>> def listSum(ls, index, result):
...     # Base condition
...     if index == len(ls):
...         return result
...
...     # Call with next index and add the current element to result
...     return listSum(ls, index + 1, result + ls[index])
... 
>>> listSum([1, 3, 4, 5, 6], 0, 0)
19

Innere Funktionsversion

Wenn Sie sich jetzt die Funktionsdefinition ansehen, übergeben Sie ihr drei Parameter. Nehmen wir an, Sie werden diese Funktion als API veröffentlichen. Wird es für die Benutzer praktisch sein, drei Werte zu übergeben, wenn sie tatsächlich die Summe einer Liste finden?

NÖ. Was können wir dagegen tun? Wir können eine andere Funktion erstellen, die lokal zum aktuellen ist listSum Funktion und wir können alle implementierungsbezogenen Parameter wie folgt an sie übergeben

>>> def listSum(ls):
...
...     def recursion(index, result):
...         if index == len(ls):
...             return result
...         return recursion(index + 1, result + ls[index])
...
...     return recursion(0, 0)
... 
>>> listSum([1, 3, 4, 5, 6])
19

Nun, wenn die listSum aufgerufen wird, gibt es nur den Rückgabewert von zurück recursion innere Funktion, die die übernimmt index und das result Parameter. Jetzt übergeben wir nur diese Werte, nicht die Benutzer von listSum. Sie müssen nur die zu bearbeitende Liste übergeben.

In diesem Fall passieren wir nicht, wenn Sie die Parameter beachten ls zu recursion aber wir verwenden es darin. ls ist von innen zugänglich recursion wegen der Verschlusseigenschaft.


Version der Standardparameter

Wenn Sie es einfach halten möchten, ohne eine innere Funktion zu erstellen, können Sie die Standardparameter wie folgt verwenden

>>> def listSum(ls, index=0, result=0):
...     # Base condition
...     if index == len(ls):
...         return result
...
...     # Call with next index and add the current element to result
...     return listSum(ls, index + 1, result + ls[index])
... 
>>> listSum([1, 3, 4, 5, 6])
19

Nun, wenn der Aufrufer keinen expliziten Wert übergibt, dann 0 wird beiden zugeordnet index und result.


Rekursives Power-Problem

Wenden wir die Ideen nun auf ein anderes Problem an. Versuchen wir zum Beispiel, die zu implementieren power(base, exponent) Funktion. Es würde den Wert von zurückgeben base zur Macht erhoben exponent.

power(2, 5) = 32
power(5, 2) = 25
power(3, 4) = 81

Wie können wir das nun rekursiv machen? Versuchen wir zu verstehen, wie diese Ergebnisse erzielt werden.

power(2, 5) = 2 * 2 * 2 * 2 * 2 = 32
power(5, 2) = 5 * 5             = 25
power(3, 4) = 3 * 3 * 3 * 3     = 81

Hmmm, also kommen wir auf die Idee. Der base mit sich selbst multipliziert, exponent mal gibt das Ergebnis. Okay, wie gehen wir es an. Versuchen wir, die Lösung mit derselben Funktion zu definieren.

power(2, 5) = 2 * power(2, 4)
            = 2 * (2 * power(2, 3))
            = 2 * (2 * (2 * power(2, 2)))
            = 2 * (2 * (2 * (2 * power(2, 1))))

Was sollte das Ergebnis sein, wenn etwas mit 1 potenziert wird? Das Ergebnis wird die gleiche Nummer sein, richtig? Wir haben unsere Grundbedingung für unsere Rekursion erhalten 🙂

            = 2 * (2 * (2 * (2 * 2)))
            = 2 * (2 * (2 * 4))
            = 2 * (2 * 8)
            = 2 * 16
            = 32

Okay, lass es uns implementieren.

>>> def power(base, exponent):
...     # Base condition, if `exponent` is lesser than or equal to 1, return `base`
...     if exponent <= 1:
...         return base
...
...     return base * power(base, exponent - 1)
... 
>>> power(2, 5)
32
>>> power(5, 2)
25
>>> power(3, 4)
81

Okay, wie wird die Tail-Call-optimierte Version davon definiert? Lassen Sie uns das aktuelle Ergebnis als Parameter an die Funktion selbst übergeben und das Ergebnis zurückgeben, wenn die Grundbedingung erfüllt ist. Halten wir es einfach und verwenden Sie direkt den Standardparameteransatz.

>>> def power(base, exponent, result=1):
...     # Since we start with `1`, base condition would be exponent reaching 0
...     if exponent <= 0:
...         return result
...
...     return power(base, exponent - 1, result * base)
... 
>>> power(2, 5)
32
>>> power(5, 2)
25
>>> power(3, 4)
81

Jetzt reduzieren wir die exponent Wert in jedem rekursiven Aufruf und mehrere result mit base und übergebe es an die rekursive power Anruf. Wir beginnen mit dem Wert 1, denn wir nähern uns dem Problem umgekehrt. Die Rekursion wird so ablaufen

power(2, 5, 1) = power(2, 4, 1 * 2)
               = power(2, 4, 2)
               = power(2, 3, 2 * 2)
               = power(2, 3, 4)
               = power(2, 2, 4 * 2)
               = power(2, 2, 8)
               = power(2, 1, 8 * 2)
               = power(2, 1, 16)
               = power(2, 0, 16 * 2)
               = power(2, 0, 32)

Seit exponent Null wird, die Grundbedingung erfüllt ist und die result wird zurückgegeben, also bekommen wir 32 🙂

  • Danke, das ist was ich suche! Aber wozu brauche ich die Rückgabe ls[0] Teil? Könnte ich nicht einfach listSum(ls[0:])

    –Sebastian S

    13. Mai 15 um 12:32 Uhr


  • @SebastianS ls[0:] ist äquivalent zu ls (also es ist ls kopieren, um genau zu sein). Infolge, listSum würde immer mit dem gleichen Argument aufgerufen werden und im Ergebnis erreichen Sie das Rekursionslimit [it’ll run infinitely].

    – Lukasz Rogalski

    13. Mai ’15 um 12:40 Uhr

  • Wenn Sie sich den gezeigten Beispielausschnitt ansehen, listSum([1, 3, 4, 5, 6]) = 1 + listSum([3, 4, 5, 6]), was ist 1 Hier? Das erste Element der Liste, an die übergeben wird listSum. Deshalb tun wir es ls[0] und was ist [3, 4, 5, 6]? Rest der Elemente aus ls (mit Ausnahme des ersten Elements), deshalb tun wir es listSum(ls[1:])

    – das vierte Auge

    13. Mai 15 um 12:43 Uhr

  • Sie könnten eine Einstellung in Betracht ziehen index und/oder result zu 0 standardmäßig. Es beseitigt die Notwendigkeit für die innere Funktion.

    – Thijs van Dien

    13. Mai 15 um 15:08 Uhr


  • Hallo @thefourtheye, vielen Dank für deine erschöpfende Antwort. Zwei Fragen habe ich zur einfacheren Variante, was folgendes bedeutet if not ls: ... return 0. Warum sollte ich das tun return ls[0] + listSum(ls[1:]) anstatt return listSum(ls[0:]). Ich habe letzteres versucht und es funktioniert nicht. Vielen Dank für Ihre Antwort

    – Andi K

    25. April 16 um 15:30 Uhr

Frühes Beenden ist typisch für rekursive Funktionen. seq ist falsch, wenn es leer ist (also wenn keine Zahlen mehr zu summieren sind).

Die Slice-Syntax ermöglicht es, eine Sequenz an eine rekursiv aufgerufene Funktion zu übergeben, ohne dass im aktuellen Schritt eine Ganzzahl verbraucht wird.

def listSum(seq):
    if not seq:
        return 0
    return seq[0] + listSum(seq[1:])

print listSum([1,3,4,5,6])  # prints 19

  • Dies mag eine dumme Frage sein, aber wie hat sich ‘seq’ aktualisiert, um die Anfangsindizes wie zuerst 1, dann 3, dann … usw. zu entfernen?

    – Jessy Weiß

    18. Februar 16 um 4:26 Uhr

  • Siehe auch: stackoverflow.com/questions/509211/…

    – Lukasz Rogalski

    18. Februar 16 um 08:21 Uhr

def listSum(L):
    """Returns a sum of integers for a list containing
    integers.
    input: list of integers
    output: listSum returns a sum of all the integers
    in L.
    """
    if L == []:
        return []
    if len(L) == 1:
        return L[0]
    else:
        return L[0] + listSum(L[1:])
print listSum([1, 3, 4, 5, 6])
print listSum([])
print listSum([8])

Andere Version:

def listSum(ls):
    ls_len = len(ls)

    # Base condition
    if ls_len==1:
        return ls[0]
    if ls_len==0:
        return None
    # ls = listSum(ls[0:i]) + listSum(ls[i:])
    elif ls_len%2==0:
            i = int(ls_len/2)
            return listSum(ls[0:i]) + listSum(ls[i:])
    else:
        i = int((ls_len-1)/2)
        return listSum(ls[0:i]) + listSum(ls[i:])

Folgen Sie dem Beispiel von @thefourtheye, wir können sagen:

listSum([1, 3, 4, 5, 6]) = listSum([1, 3]) + listSum([4, 5, 6])
                         = (listSum([1]) + listSum([3])) + (listSum([4]) + listSum([5, 6]))
                         = (listSum([1]) + listSum([3])) + (listSum([4]) + (listSum([5]) + listSum([6])))

Grundzustand: wann ls nur ein Element hat, gib diesen Wert zurück.

def listsum(list):
    if len(list) == 1:
        return list[0]
    else:
        return list[0] + listsum(list[1:])

print(listsum([1,5,9,10,20]))

Die Grundidee hinter dieser rekursiven Funktion ist, dass wir prüfen möchten, ob wir einen Basisfall haben, der als angezeigt wird if len(list) == 1:. Für den Basisfall geben wir einfach den Wert in der Liste zurück return list[0], andernfalls haben wir immer noch mehrere Elemente in der Liste. Im else: Anweisung werden wir das erste Element aus der Liste hinzufügen, das ist list[0] zu den restlichen Elementen in der Liste. Dies wird gezeigt, indem die Funktion rekursiv aufgerufen wird, wobei die Liste um 1 Element kürzer ist – das Element am Index 0 – listsum(list[1:]), wiederholt sich dieser Vorgang, wobei die Liste kleiner wird, bis Sie beim Basisfall ankommen – einer Liste der Länge 1, und dann erhalten Sie ein Endergebnis.

.

784990cookie-checkGrundlagen der Rekursion in Python

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy