Wie berechnet man rekursiv die Summe der Elemente in einer Liste in Python?

Grundlagen der Rekursion in Python

Rekursion ist eine leistungsstarke Technik in der Informatik, bei der sich eine Funktion selbst aufruft, um ein Problem zu lösen. In diesem Zusammenhang befassen wir uns mit der Frage der Entwicklung einer rekursiven Python-Funktion namens „listSum“, um die Summe aller ganzen Zahlen in einer bestimmten Liste zu bestimmen.

Betrachten Sie das Problem: „Schreiben Sie eine rekursive Funktion, ‚listSum‘.“ das nimmt eine Liste von ganzen Zahlen und gibt die Summe aller ganzen Zahlen in der Liste zurück. In diesem Szenario kann das Ergebnis erhalten werden, indem die erste Zahl zum Ergebnis der Anwendung derselben Funktion auf die verbleibenden Elemente der Liste addiert wird. Zum Beispiel:

In diesem Beispiel ist die Basisbedingung listSum([]), was eine leere Liste darstellt. Da eine leere Liste keine zu summierenden Elemente enthält, ist ihr Ergebnis 0.

Implementierung von listSum

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

In dieser Implementierung prüfen wir, ob eine leere Liste als Grundbedingung dient, und geben 0 zurück. Bei Listen mit Elementen fügen wir das erste Element zum rekursiven Ergebnis der verbleibenden Elemente hinzu.

Tail Call Recursion

<code class="python">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:])</code>

Zur Optimierung können wir vermeiden, uns auf den Rückgabewert des vorherigen rekursiven Aufrufs zu verlassen . Durch die Übergabe des Ergebnisses als Parameter können wir den Wert sofort zurückgeben, wenn die Grundbedingung erfüllt ist:

Diese Version akkumuliert effektiv die Summe im Parameter „Ergebnis“ und gibt sie zurück, wenn die Grundbedingung erfüllt ist .

Index weitergeben

<code class="python">def listSum(ls, result):
    if not ls:
        return result
    return listSum(ls[1:], result + ls[0])</code>

Um die Erstellung von Zwischenlisten zu vermeiden, können wir den Index des aktuellen Elements übergeben:

Die Basisbedingung prüft, ob der Index erreicht ist das Ende der Liste.

Innere Funktionsversion

<code class="python">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])</code>

Um die Parameterbehandlung zu vereinfachen, können wir eine innere Funktion erstellen, um die Rekursion zu verarbeiten:

Standardparameterversion

Der Einfachheit halber können wir Standardparameter verwenden:

<code class="python">def listSum(ls):
    def recursion(index, result):
        if index == len(ls):
            return result
        return recursion(index + 1, result + ls[index])

    return recursion(0, 0)</code>

Das obige ist der detaillierte Inhalt vonWie berechnet man rekursiv die Summe der Elemente in einer Liste in Python?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!