Grundlagen der Rekursion in Python

“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.

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 🙂

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

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.