Schwanzrekursion in Python

1. Rekursion in Python
2. Schwanzrekursion in Python
3. Rufen Sie die tailrekursive Funktion in Python auf
4. Vorteile von schwanzrekursiven Funktionen

Im heutigen Tutorial lernen wir etwas über die Schwanzrekursion, indem wir die Rekursion und ihre Typen durchgehen. Darüber hinaus werden wir auch lernen, wie man Tail-Rekursion in Python aufruft, und einige Vorteile seiner Verwendung untersuchen.

Rekursion in Python

In der Informatik ist Rekursion eine Problemlösungsmethode, bei der sich eine Funktion im Körper selbst aufruft, bis eine bestimmte Bedingung erfüllt ist.

Es ist eine der wertvollsten Methoden und hat viele Anwendungsfälle aus dem wirklichen Leben; Es hat jedoch einige Einschränkungen, und das ist seine räumliche und zeitliche Komplexität. Sehen wir uns unten ein Beispiel für eine Rekursion an.

Beispielcode:

def factorial(n):
    if n == 1 or n == 0:
        return 1
    else:
        return n * factorial(n - 1)  # recursive call


num = 4

# In this case factorial is 4x3x2x1 = 24
print(f"The factorial of {num} is {factorial(num)}")

Ausgang:

The factorial of 4 is 24

Rekursion verwendet einen Stack, um die lokalen Variablen zu halten, jeder Rekursionslauf erhöht seine Größe, und die Stack-Größe ist begrenzt. Aus diesem Grund haben die Entwickler begonnen, über einige optimierte Lösungen nachzudenken.

Es ist nur für kleine Zahlen geeignet; Aus diesem Grund haben die Entwickler die optimierte Lösung der einfachen Rekursion entwickelt, und das ist Tail Recursion.

Arten von Rekursionen

Bei rekursiven Funktionen gibt es zwei Haupttypen:

1. Kopfrekursion
2. Schwanzrekursion

Bei Kopfrekursion ruft sich die Funktion am Anfang selbst auf, bei Endrekursion ruft sich eine Funktion am Ende der Rekursion selbst auf.

Beide haben Vor- und Nachteile, aber die Schwanzrekursion wird im Allgemeinen als effizienter angesehen. Lassen Sie es uns unten genauer verstehen.

Schwanzrekursion in Python

Tail recursion in Python ist eine optimierte Lösung für einfache Rekursion; es erlaubt eine unbegrenzte Rekursion, ohne einen Stapelüberlauffehler auszulösen.

Aber bevor wir auf die Details der Tail-Call-Rekursion eingehen, wollen wir die Definition der Tail-Call-Rekursion verstehen. Der Aufruf bedeutet, dass wir erwägen, die Funktion aufzurufen, während der Schwanz bedeutet, dass die letzte. Das Aufrufen der tail-rekursiven Methode bedeutet also, dass die Funktion sich selbst am Ende der Funktion wiederholt aufruft.

Heutzutage sind die meisten Programmiersprachen schwanzrekursiv, was bedeutet, dass sie Optimierungen an den rekursiven Funktionen vornehmen.

Rufen Sie die tailrekursive Funktion in Python auf

Es gibt zwei Möglichkeiten, eine Tail-rekursive Funktion in Python aufzurufen. Die erste besteht darin, das Schlüsselwort return zu verwenden, und die zweite besteht darin, das Schlüsselwort yield zu verwenden.

Verwenden Sie das Schlüsselwort return, um eine tail-rekursive Funktion aufzurufen

Erstens können Sie das Schlüsselwort return verwenden, um einen Wert von einer Funktion zurückzugeben. Sie müssen jedoch mit diesem Schlüsselwort vorsichtig sein, da es die Funktion sofort beendet.

Das bedeutet, dass Sie es nur verwenden können, wenn Sie sicher sind, dass die Funktion nie wieder aufgerufen werden muss. Denken Sie daran, wenn wir das Schlüsselwort return verwenden, gibt die Funktion den zuletzt berechneten Wert zurück.

Dies ist die gebräuchlichste Art, eine endrekursive Funktion aufzurufen. Sehen Sie sich beispielsweise unten einen Codezaun an.

Beispielcode:

def trisum(n, csum):
    while True:  # Change recursion to a while loop
        if n == 0:
            return csum
        n, csum = n - 1, csum + n  # Update parameters instead of tail recursion


trisum(1000, 0)

Ausgang:

500500

Verwenden Sie das Schlüsselwort yield, um eine tail-rekursive Funktion aufzurufen

Eine andere Möglichkeit, endrekursive Funktionen aufzurufen, ist die Verwendung des Schlüsselworts yield. Mit diesem Schlüsselwort können Sie einen Wert von einer Funktion zurückgeben, ohne die Funktion zu beenden.

Sie können die Funktion wiederholt aufrufen und jedes Mal einen anderen Wert zurückgeben. Dies ist praktisch für Funktionen, die eine große Anzahl von Werten zurückgeben müssen.

Wenn Sie das Schlüsselwort yield verwenden, ergibt die Funktion den zuletzt berechneten Wert. Es ist eine weniger gebräuchliche Art, eine Tail-rekursive Funktion aufzurufen, aber es kann in einigen Fällen hilfreich sein.

Beispielcode:

def lprint(a):
    if isinstance(a, list):
        for i in a:
            yield from lprint(i)
    else:
        yield a


b = [[1, [2, 3], 4], [5, 6, [7, 8, [9]]]]
for i in lprint(b):
    print(i)

Ausgang:

1
2
3
4
5
6
7
8
9

Vorteile von schwanzrekursiven Funktionen

Tail-rekursive Funktionen sind eine Art rekursiver Funktion, bei der die letzte Anweisung in der Funktion ein Aufruf der rekursiven Funktion ist.

Diese Funktion ist effizienter als rekursive Funktionen ohne Ende, da die Funktion die Zwischenwerte der rekursiven Aufrufe nicht verfolgen muss.

Es macht endrekursive Funktionen effizienter und leichter verständlich. Die Verwendung von endrekursiven Funktionen bietet viele Vorteile.

1. Einer der Hauptvorteile der Schwanzrekursion ist, dass sie einfacher zu optimieren ist. Da der Tail-Aufruf das Letzte ist, was in der Funktion passiert, kann der Compiler ihn leichter optimieren. Dies bedeutet, dass rekursive Endfunktionen in Bezug auf Zeit und Platz effizienter sein können.
2. Ein weiterer Vorteil der Schwanzrekursion ist, dass sie oft einfacher zu verstehen ist. Da der rekursive Aufruf das Letzte ist, was in der Funktion passiert, ist es einfacher zu sehen, was passiert. Es kann das Debuggen und Warten von rekursiven Endfunktionen erleichtern.
3. Sie sind effizienter als rekursive Funktionen ohne Ende, da sie die Notwendigkeit vermeiden, Zwischenwerte zu verfolgen.
4. Sie sind einfacher zu begründen, weil der Funktionsaufrufstapel am Ende der Funktion immer leer ist. Außerdem können schwanzrekursive Funktionen einfacher parallelisiert werden.
5. Wir können sie leicht in iterative Programme umwandeln, was in manchen Fällen effizienter sein kann.
6. Es kann die Funktion beschleunigen und weniger Speicher verbrauchen. Außerdem kann es einfacher werden, korrekten Code zu schreiben.