Python Language
Rekursion

Bemerkungen

Summe der Zahlen von 1 bis n

Wenn ich die Summe der Zahlen von 1 bis n herausfinden wollte, wobei n eine natürliche Zahl ist, kann ich 1 + 2 + 3 + 4 + ... + (several hours later) + n . Alternativ könnte ich eine for Schleife schreiben:

n = 0
for i in range (1, n+1):
    n += i

Oder ich könnte eine als Rekursion bekannte Technik verwenden:

def recursion(n):
    if n == 1:
        return 1
    return n + recursion(n - 1)

Rekursion hat Vorteile gegenüber den beiden obigen Methoden. Rekursion benötigt weniger Zeit als das Herausschreiben von 1 + 2 + 3 für eine Summe von 1 bis 3. Bei recursion(4) kann Rekursion zum Rückwärtsarbeiten verwendet werden:

Funktionsaufrufe: (4 -> 4 + 3 -> 4 + 3 + 2 -> 4 + 3 + 2 + 1 -> 10)

Während die for Schleife streng vorwärts arbeitet: (1 -> 1 + 2 -> 1 + 2 + 3 -> 1 + 2 + 3 + 4 -> 10). Manchmal ist die rekursive Lösung einfacher als die iterative Lösung. Dies ist offensichtlich, wenn eine Stornierung einer verknüpften Liste implementiert wird.

Was, Wie und Wann der Rekursion

Rekursion tritt auf, wenn ein Funktionsaufruf bewirkt, dass dieselbe Funktion erneut aufgerufen wird, bevor der ursprüngliche Funktionsaufruf beendet wird. Betrachten Sie zum Beispiel den bekannten mathematischen Ausdruck x! (dh die faktorielle Operation). Die faktorielle Operation wird für alle nicht negativen Ganzzahlen wie folgt definiert:

• Wenn die Zahl 0 ist, lautet die Antwort 1.
• Andernfalls lautet die Antwort: Diese Zahl multipliziert mit der Fakultät einer Zahl, die kleiner als diese Zahl ist.

In Python kann eine naive Implementierung der faktoriellen Operation als Funktion wie folgt definiert werden:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

Rekursionsfunktionen sind manchmal schwer zu verstehen, gehen wir also Schritt für Schritt durch. Betrachten Sie die Ausdrucksfaktor factorial(3) . Dies und alle Funktionsaufrufe schaffen eine neue Umgebung . Eine Umgebung ist im Grunde nur eine Tabelle, die Bezeichner (z. B. n , factorial , print usw.) ihren entsprechenden Werten zuordnet. Sie können jederzeit mit locals() auf die aktuelle Umgebung zugreifen. Beim ersten Funktionsaufruf wird als einzige lokale Variable n = 3 . Daher würde das Drucken von locals() {'n': 3} . Da n == 3 , wird der Rückgabewert zu n * factorial(n - 1) .

In diesem nächsten Schritt können die Dinge etwas verwirrend werden. Wenn wir unseren neuen Ausdruck betrachten, wissen wir bereits, was n ist. Wir wissen jedoch noch nicht, was factorial(n - 1) ist. Zuerst wird n - 1 zu 2 ausgewertet. Dann wird 2 als Wert für n an factorial . Da dies ein neuer Funktionsaufruf ist, wird eine zweite Umgebung zum Speichern dieses neuen n . Sei A die erste Umgebung und B die zweite Umgebung. A existiert immer noch und ist gleich {'n': 3} , jedoch ist B (was gleich {'n': 2} ) die aktuelle Umgebung. Betrachtet man den Funktionsrumpf, so ist der Rückgabewert wiederum n * factorial(n - 1) . Ohne diesen Ausdruck auszuwerten, setzen wir ihn in den ursprünglichen Rückgabeausdruck ein. Auf diese Weise verwerfen wir B geistig. Erinnern Sie sich also daran, n entsprechend zu ersetzen (dh Verweise auf B 's n werden durch n - 1 , das A ' s n ). Nun wird der ursprüngliche Rückgabeausdruck zu n * ((n - 1) * factorial((n - 1) - 1)) . Nehmen Sie sich eine Sekunde Zeit, um sich zu vergewissern, warum dies so ist.

Nun wollen wir den factorial((n - 1) - 1)) bewerten. Da A n == 3 , übergeben wir 1 in factorial . Daher erstellen wir eine neue Umgebung C, die gleich {'n': 1} . Der Rückgabewert ist wiederum n * factorial(n - 1) . Ersetzen Sie also die factorial((n - 1) - 1)) des "ursprünglichen" Rückgabeausdrucks ähnlich wie zuvor den ursprünglichen Rückgabeausdruck angepasst. Der "ursprüngliche" Ausdruck ist jetzt n * ((n - 1) * ((n - 2) * factorial((n - 2) - 1))) .

Fast fertig. Nun müssen wir die factorial((n - 2) - 1) bewerten. Diesmal übergeben wir 0 . Daher wird dies mit 1 bewertet. Lassen Sie uns nun unsere letzte Ersetzung durchführen. Der "ursprüngliche" Rückkehrausdruck ist jetzt n * ((n - 1) * ((n - 2) * 1)) . Unter Hinweis darauf, dass der ursprüngliche Rückgabeausdruck unter A ausgewertet wird, wird der Ausdruck zu 3 * ((3 - 1) * ((3 - 2) * 1)) . Dies wird natürlich mit 6 bewertet. Um zu bestätigen, dass dies die richtige Antwort ist, erinnern Sie sich an 3! == 3 * 2 * 1 == 6 . Vergewissern Sie sich vor dem Lesen, dass Sie das Konzept der Umgebungen und deren Anwendung für die Rekursion vollständig verstehen.

Die Anweisung if n == 0: return 1 wird als Basisfall bezeichnet. Dies liegt daran, dass es keine Rekursion zeigt. Ein Basisfall ist unbedingt erforderlich. Ohne eins stoßen Sie auf unendliche Rekursion. Solange Sie mindestens einen Basisfall haben, können Sie so viele Fälle haben, wie Sie möchten. Zum Beispiel könnten wir eine gleichwertige factorial wie folgt schreiben:

def factorial(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        return n * factorial(n - 1)

Sie können auch mehrere Rekursionsfälle haben, aber wir werden nicht darauf eingehen, da dies relativ ungewöhnlich ist und es oft schwierig ist, sie mental zu verarbeiten.

Sie können auch "parallele" rekursive Funktionsaufrufe durchführen. Betrachten Sie zum Beispiel die Fibonacci-Sequenz, die wie folgt definiert ist:

• Wenn die Zahl 0 ist, lautet die Antwort 0.
• Wenn die Nummer 1 ist, lautet die Antwort 1.
• Ansonsten ist die Antwort die Summe der vorherigen zwei Fibonacci-Zahlen.

Wir können dies wie folgt definieren:

def fib(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib(n - 2) + fib(n - 1)

Ich werde diese Funktion nicht so gründlich durchlaufen wie bei factorial(3) , aber der endgültige Rückgabewert von fib(5) entspricht dem folgenden ( syntaktisch ungültigen) Ausdruck:

(
  fib((n - 2) - 2)
  +
  (
    fib(((n - 2) - 1) - 2)
    +
    fib(((n - 2) - 1) - 1)
  )
)
+
(
  (
    fib(((n - 1) - 2) - 2)
    +
    fib(((n - 1) - 2) - 1)
  )
  +
  (
    fib(((n - 1) - 1) - 2)
    +
    (
      fib((((n - 1) - 1) - 1) - 2)
      +
      fib((((n - 1) - 1) - 1) - 1)
    )
  )
)

Dies wird zu (1 + (0 + 1)) + ((0 + 1) + (1 + (0 + 1))) was natürlich mit 5 bewertet wird.

Lassen Sie uns nun ein paar weitere Vokabelthemen behandeln:

• Ein Abbruchaufruf ist einfach ein rekursiver Funktionsaufruf, bei dem es sich um die zuletzt ausgeführte Operation handelt, bevor ein Wert zurückgegeben wird. Um klar zu sein, ist return foo(n - 1) ein Rückruf, aber return foo(n - 1) + 1 nicht (da der Zusatz die letzte Operation ist).
• Die Rückrufoptimierung (TCO) ist eine Möglichkeit, Rekursion in rekursiven Funktionen automatisch zu reduzieren.
• Tail Call Elimination (TCE) ist die Reduzierung eines Tail Call auf einen Ausdruck, der ohne Rekursion ausgewertet werden kann. TCE ist eine Art TCO.

Die Optimierung von Rückrufen ist aus mehreren Gründen hilfreich:

• Der Interpreter kann den von Umgebungen belegten Speicherplatz minimieren. Da kein Computer über unbegrenzten Speicher verfügt, würden übermäßige rekursive Funktionsaufrufe zu einem Stapelüberlauf führen .
• Der Interpreter kann die Anzahl der Stack-Frame- Switches reduzieren.

Python hat aus verschiedenen Gründen keine TCO-Form implementiert. Daher sind andere Techniken erforderlich, um diese Einschränkung zu umgehen. Die Methode der Wahl hängt vom Anwendungsfall ab. Mit einiger Intuition können die Definitionen von factorial und fib relativ leicht in iterativen Code wie folgt konvertiert werden:

def factorial(n):
    product = 1
    while n > 1:
        product *= n
        n -= 1
    return product

def fib(n):
    a, b = 0, 1
    while n > 0:
        a, b = b, a + b
        n -= 1
    return a

Dies ist in der Regel die effizienteste Möglichkeit, Rekursion manuell zu eliminieren, bei komplexeren Funktionen kann dies jedoch sehr schwierig werden.

Ein weiteres nützliches Werkzeug ist der lru_cache- Dekorator von Python, mit dem die Anzahl der redundanten Berechnungen reduziert werden kann.

Sie haben jetzt eine Idee, wie Sie Rekursion in Python vermeiden können, aber wann sollten Sie Rekursion verwenden? Die Antwort lautet "nicht oft". Alle rekursiven Funktionen können iterativ implementiert werden. Es geht einfach darum, herauszufinden, wie das geht. In seltenen Fällen ist Rekursion jedoch in Ordnung. Rekursion ist in Python üblich, wenn die erwarteten Eingaben keine signifikante Anzahl rekursiver Funktionsaufrufe verursachen würden.

Wenn Rekursion ein Thema ist, das Sie interessiert, bitte ich Sie, funktionale Sprachen wie Scheme oder Haskell zu lernen. In solchen Sprachen ist Rekursion viel nützlicher.

Bitte beachten Sie, dass das obige Beispiel für die Fibonacci-Sequenz zwar gut geeignet ist, um zu zeigen, wie die Definition in Python angewendet wird und später der Lru-Cache verwendet wird, eine ineffiziente Laufzeit aufweist, da für jeden Nicht-Basisfall zwei rekursive Aufrufe erfolgen. Die Anzahl der Aufrufe der Funktion steigt exponentiell auf n .
Nicht intuitiv würde eine effizientere Implementierung eine lineare Rekursion verwenden:

def fib(n):
    if n <= 1:
        return (n,0)
    else:
        (a, b) = fib(n - 1)
        return (a + b, a)

Aber dieser hat die Ausgabe eines Zahlenpaares . Dies unterstreicht, dass einige Funktionen von Rekursion wirklich nicht viel profitieren.

Baumerkundung mit Rekursion

Sagen wir, wir haben den folgenden Baum:

root
- A
  - AA
  - AB
- B
  - BA
  - BB
    - BBA

Wenn wir nun alle Namen der Elemente auflisten möchten, können Sie dies mit einer einfachen for-Schleife tun. Wir nehmen an, dass es eine Funktion get_name() , um eine Zeichenfolge des Namens eines Knotens zurückzugeben, eine Funktion get_children() , um eine Liste aller get_children() eines gegebenen Knotens in der Baumstruktur zurückzugeben, und eine Funktion get_root() an Holen Sie sich den Wurzelknoten.

root = get_root(tree)
for node in get_children(root):
    print(get_name(node))
    for child in get_children(node):
        print(get_name(child))
        for grand_child in get_children(child):
            print(get_name(grand_child))
# prints: A, AA, AB, B, BA, BB, BBA

Dies funktioniert gut und schnell, aber was ist, wenn die Unterknoten eigene Unterknoten bekommen? Und diese Unterknoten könnten weitere Unterknoten haben ... Was ist, wenn Sie nicht vorher wissen, wie viele es gibt? Eine Methode, um dieses Problem zu lösen, ist die Verwendung von Rekursion.

def list_tree_names(node):
    for child in get_children(node):
        print(get_name(child))
        list_tree_names(node=child)

list_tree_names(node=get_root(tree))
# prints: A, AA, AB, B, BA, BB, BBA

Vielleicht möchten Sie nicht drucken, sondern eine einfache Liste aller Knotennamen zurückgeben. Dies kann durch Übergeben einer Rolling List als Parameter erfolgen.

def list_tree_names(node, lst=[]):
    for child in get_children(node):
        lst.append(get_name(child))
        list_tree_names(node=child, lst=lst)
    return lst

list_tree_names(node=get_root(tree))
# returns ['A', 'AA', 'AB', 'B', 'BA', 'BB', 'BBA']

Maximale Rekursionstiefe erhöhen

Die Tiefe der möglichen Rekursion ist begrenzt, abhängig von der Python-Implementierung. Wenn der Grenzwert erreicht ist, wird eine RuntimeError-Ausnahme ausgelöst:

RuntimeError: Maximum Recursion Depth Exceeded

Hier ist ein Beispiel eines Programms, das diesen Fehler verursachen würde:

def cursing(depth):
  try:
    cursing(depth + 1) # actually, re-cursing
  except RuntimeError as RE:
    print('I recursed {} times!'.format(depth))
cursing(0)
# Out: I recursed 1083 times!

Sie können die Rekursionstiefenbegrenzung mit ändern

sys.setrecursionlimit(limit) 

Sie können die aktuellen Parameter des Grenzwerts überprüfen, indem Sie Folgendes ausführen:

sys.getrecursionlimit()

Die gleiche Methode wie oben beschrieben mit unserem neuen Limit erhalten wir

sys.setrecursionlimit(2000)
cursing(0)
# Out: I recursed 1997 times!

Bei Python 3.5 ist die Ausnahme ein RecursionError, der von RuntimeError abgeleitet wird.

Schwanzrekursion - schlechte Praxis

Wenn das einzige, was von einer Funktion zurückgegeben wird, ein rekursiver Aufruf ist, wird dies als rekursive Rekursion bezeichnet.

Hier ein Beispiel für einen Countdown, der mit der Rekursion des Endes geschrieben wurde:

def countdown(n):
    if n == 0:
        print "Blastoff!"
    else:
        print n
        countdown(n-1)

Jede Berechnung, die unter Verwendung der Iteration durchgeführt werden kann, kann auch unter Verwendung der Rekursion durchgeführt werden. Hier ist eine Version von find_max, die mit Tail-Rekursion geschrieben wurde:

def find_max(seq, max_so_far):
    if not seq:
        return max_so_far
    if max_so_far < seq[0]:
        return find_max(seq[1:], seq[0])
    else:
        return find_max(seq[1:], max_so_far)

Die Tail-Rekursion wird in Python als schlechte Praxis betrachtet, da der Python-Compiler die Optimierung für rekursive Tails-Aufrufe nicht behandelt. Die rekursive Lösung verwendet in solchen Fällen mehr Systemressourcen als die entsprechende iterative Lösung.

Rekursionsoptimierung durch Stack-Introspection

Standardmäßig darf der Rekursionsstapel von Python 1000 Frames nicht überschreiten. Sie können dies ändern, indem Sie sys.setrecursionlimit(15000) setzen. sys.setrecursionlimit(15000) ist jedoch schneller, da diese Methode mehr Speicher verbraucht. Stattdessen können wir das Problem der Tail-Rekursion auch durch Stack-Introspection lösen.

#!/usr/bin/env python2.4
# This program shows off a python decorator which implements tail call optimization. It
# does this by throwing an exception if it is it's own grandparent, and catching such 
# exceptions to recall the stack.

import sys

class TailRecurseException:
    def __init__(self, args, kwargs):
        self.args = args
        self.kwargs = kwargs

def tail_call_optimized(g):
"""
This function decorates a function with tail call
optimization. It does this by throwing an exception
if it is it's own grandparent, and catching such
exceptions to fake the tail call optimization.
  
This function fails if the decorated
function recurses in a non-tail context.
"""
      
    def func(*args, **kwargs):
        f = sys._getframe()
        if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
            raise TailRecurseException(args, kwargs)
        else:
            while 1:
                try:
                    return g(*args, **kwargs)
                except TailRecurseException, e:
                    args = e.args
                    kwargs = e.kwargs
    func.__doc__ = g.__doc__
    return func

Um die rekursiven Funktionen zu optimieren, können wir den @tail_call_optimized Dekorator verwenden, um unsere Funktion aufzurufen. Hier einige der häufigsten Rekursionsbeispiele, die den oben beschriebenen Dekorator verwenden:

Fakultätsbeispiel:

@tail_call_optimized
def factorial(n, acc=1):
  "calculate a factorial"
  if n == 0:
    return acc
  return factorial(n-1, n*acc)

print factorial(10000)
# prints a big, big number,
# but doesn't hit the recursion limit.

Fibonacci-Beispiel:

@tail_call_optimized
def fib(i, current = 0, next = 1):
  if i == 0:
    return current
  else:
    return fib(i - 1, next, current + next)

print fib(10000)
# also prints a big number,
# but doesn't hit the recursion limit.