Wie implementiert man eine Tail-Call-Rekursion für eine effiziente Summierung in Python?

Rekursion in Python: Ein Leitfaden zum Verständnis

Rekursive Funktion zum Summieren einer Liste von ganzen Zahlen

Nehmen wir an, wir müssen eine rekursive Funktion namens erstellen „listSum“, das die Summe aller Ganzzahlen in einer Liste berechnet. Ziel ist es, dies ohne die Verwendung integrierter Funktionen zu erreichen. Zuerst sollten wir darüber nachdenken, wie wir das Ergebnis der Funktion in Bezug auf sich selbst ausdrücken können.

In diesem Fall können wir das Ergebnis erhalten, indem wir die erste Zahl mit dem Ergebnis des Aufrufs derselben Funktion mit addieren Rest der Elemente in der Liste. Rekursiv kann dies wie folgt ausgedrückt werden:

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

Der Basisfall für die Rekursion ist, wenn die Liste leer wird, ein Ereignis, das ein Ergebnis von 0 erfordert. Implementierung dieses Ansatzes in Python-Code:

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

Tail Call Recursion

Die vorherige Implementierung hängt vom Wert des vorherigen Funktionsaufrufs ab, um das tatsächliche Ergebnis zu berechnen. Dies kann mithilfe der Tail-Call-Rekursion verbessert werden:

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

Durch die Einführung eines zusätzlichen Parameters result akkumulieren wir die darin enthaltene Summe und geben sie zurück, wenn die Grundbedingung erfüllt ist.

Index weitergeben

Um die Erstellung mehrerer Zwischenlisten zu vermeiden, können wir den Index des zu verarbeitenden Elements weitergeben:

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

Die Basisbedingung prüft, ob der Index die Länge der Liste erreicht hat.

Version der inneren Funktion

Um die Parameterübergabe zu vereinfachen, können wir eine innere Funktion 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>

Die Rekursion der inneren Funktion akzeptiert die Index- und Ergebnisparameter und listSum gibt zurück das Ergebnis des Aufrufs der inneren Funktion mit Anfangswerten.

Version der Standardparameter

Die Verwendung von Standardparametern ist eine weitere Vereinfachung:

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

Standardwerte werden dem Index und zugewiesen Ergebnis, wenn vom Aufrufer nicht explizit angegeben.

Problem der rekursiven Potenz

Betrachten Sie das Problem der Berechnung der Potenz (Basis, Exponent), das den Wert der Basis potenziert mit dem Exponenten zurückgibt. Rekursiv können wir die Lösung 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))))

Die Basisbedingung ist, wenn der Exponent 1 oder weniger wird. In diesem Fall ist das Ergebnis die Basis selbst:

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

Implementierung in Python :

<code class="python">def power(base, exponent):
    if exponent <= 1:
        return base
    return base * power(base, exponent - 1)</code>

Verwendung von Standardparametern für die Tail Call Optimized-Version:

<code class="python">def power(base, exponent, result=1):
    if exponent <= 0:
        return result
    return power(base, exponent - 1, result * base)</code>

Das obige ist der detaillierte Inhalt vonWie implementiert man eine Tail-Call-Rekursion für eine effiziente Summierung in Python?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!