Grundlagen der Rekursion in Python

Question

"Schreiben Sie eine rekursive Funktion," listSum ", die eine Liste von Ganzzahlen nimmt und die Summe aller Ganzzahlen in der Liste zurückgibt".

Beispiel:

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

Ich weiß, wie diese eine andere Art und Weise zu tun, aber nicht in der rekursiven Art und Weise.

Ich brauche den grundlegenden Weg, dies zu tun, da spezielle eingebaute Funktionen nicht erlaubt ist.

Answer 1

Immer wenn Sie auf ein Problem wie dieses stoßen, versuchen Sie, das Ergebnis der Funktion mit der gleichen Funktion auszudrücken.

In Ihrem Fall können Sie das Ergebnis erhalten, indem Sie die erste Zahl mit dem Ergebnis des Aufrufs der gleichen Funktion mit dem Rest der Elemente in der Liste hinzufügen.

Zum Beispiel

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 das Ergebnis der listSum([]) sein sollte? Es sollte 0 sein. Das heißt Grundzustand Ihrer Rekursion. Wenn die Basisbedingung erfüllt ist, wird die Rekursion zu einem Ende kommen. Versuchen wir nun, es zu implementieren.

Die Hauptsache hier ist, die Liste aufzuteilen. Sie können dazu 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 

---

Endaufruf Rekursion

Wenn Sie verstehen, wie die obigen Rekursion funktioniert, können Sie versuchen, es ein bisschen besser zu machen. Um nun das tatsächliche Ergebnis zu finden, sind wir auch auf den Wert der vorherigen Funktion angewiesen. Die return-Anweisung kann den Wert nicht sofort zurückgeben, bis der rekursive Aufruf ein Ergebnis zurückgibt. Wir können diesen durch vermeiden, um den Strom zu den Funktionsparametern übergeben, wie diese

>>> 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 gehen wir, was der Anfangswert der Summe in den Parametern zu sein, die Null in listSum([1, 3, 4, 5, 6], 0) ist. Dann, wenn die Basisbedingung erfüllt ist, akkumulieren wir tatsächlich die Summe in dem result Parameter, so dass wir es zurückgeben. Jetzt hat die letzte return Anweisung listSum(ls[1:], result + ls[0]), wo wir das erste Element zum aktuellen result hinzufügen und es erneut an den rekursiven Aufruf übergeben.

Dies könnte eine gute Zeit sein zu verstehen Tail Call.Es wäre für Python nicht relevant, da es keine Tail-Call-Optimierung durchführt.

---

Passing um Index-Version

Nun könnte man denken, dass wir so viele Zwischenlisten erstellen. Kann ich das vermeiden?

Natürlich können Sie. Sie brauchen nur den Index des Artikels, der als nächstes verarbeitet werden soll. Aber jetzt wird die Grundbedingung anders sein. Da wir den Index weitergeben werden, wie werden wir feststellen, wie die gesamte Liste verarbeitet wurde? Nun, wenn der Index gleich der Länge der Liste ist, dann haben wir alle Elemente darin 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 

---

Inner Funktion Version

Wenn Sie bei der Funktionsdefinition aussehen jetzt, Sie übergeben drei Parameter zu. Nehmen wir an, Sie werden diese Funktion als API freigeben. Wird es für die Benutzer bequem sein, drei Werte zu übergeben, wenn sie tatsächlich die Summe einer Liste finden?

Nein. Was können wir dagegen tun? Wir können eine andere Funktion erstellen, die auf die tatsächliche listSum Funktion lokal ist, und wir können alle Implementierung bezogenen Parameter, um es, wie diese

>>> 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 passieren, wenn die listSum genannt wird, es gibt nur den Rückgabewert recursion innere Funktion, die die index und die result Parameter akzeptiert. Jetzt übergeben wir nur diese Werte, nicht die Benutzer von listSum. Sie müssen nur die zu verarbeitende Liste passieren.

In diesem Fall, wenn Sie die Parameter beobachten, übergeben wir ls nicht an recursion, aber wir verwenden es darin. ls ist innerhalb recursion aufgrund der Verschluss-Eigenschaft zugänglich.

---

Standardparameter Version

Nun, wenn Sie es einfach halten möchten, ohne eine innere Funktion zu erstellen, können Sie die Verwendung der Standardparameter, wie diese

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

machen Wenn nun der Aufrufer keinen Wert explizit übergibt, wird 0 sowohl index als auch result zugewiesen.

---

rekursive Netz Problem

Nun läßt die Ideen zu einem anderen Problem anwenden. Versuchen Sie beispielsweise, die power(base, exponent)-Funktion zu implementieren. Es würde den Wert von base auf die Leistung exponent erhöht zurückgegeben.

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

Nun, wie können wir das rekursiv tun? Lassen Sie uns versuchen zu verstehen, wie diese Ergebnisse erreicht 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, so kommen wir auf die Idee. Die base multipliziert mit sich selbst, exponent mal gibt das Ergebnis. Okay, wie nähern wir uns dem? 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 alles an Strom 1 erhöht? Ergebnis wird die gleiche Nummer sein, oder? Wir haben unsere Grundbedingung für unsere Rekursion :-)

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

In Ordnung, lässt es sich 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? Lässt das aktuelle Ergebnis als Parameter an die Funktion selbst übergeben und gibt das Ergebnis zurück, wenn die Basisbedingung erfüllt ist. Lassen Sie uns es einfach halten und den Standardparameteransatz direkt verwenden.

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

Nun reduzieren wir den exponent Wert in jedem rekursiven Aufruf und mehrere result mit base und an die rekursive power Aufruf übergeben. Wir beginnen mit dem Wert 1, weil wir uns dem Problem in umgekehrter Richtung nähern. Die Rekursion wird wie das passieren

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) 

Da exponent Null wird, wird die Basisbedingung erfüllt und die result wird zurückgegeben, so dass wir 32 :-)

Answer 2

Early-Exit ist typisch für rekursive Funktionen. seq ist falsch, wenn leer (daher wenn keine Zahlen mehr übrig sind).

Slice-Syntax ermöglicht die Übergabe der Sequenz an rekursiv aufgerufene Funktion ohne Integer im aktuellen Schritt.

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

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

Answer 3

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])