Rekursion in Python verstehen: Werden Sie sich damit auseinandersetzen?

Rekursion ist ein grundlegendes Konzept in der Programmierung, aber manchmal kann es etwas mysteriös erscheinen. Vereinfachen wir es also und sehen wir, dass es einfacher ist, als es scheint!

Was ist Rekursion?

Rekursion ist, wenn eine Funktion ein Problem löst, indem sie... sich selbst aufruft! Ja, das stimmt. Es funktioniert wie eine Geschichte, die man immer wieder erzählt, nur jedes Mal etwas kürzer, bis man am Ende angelangt ist. Aber damit es richtig funktioniert, muss es zwei goldene Regeln erfüllen:

1. Beendigungsbedingung: Dies ist der Punkt, an dem die Funktion anhalten muss, sonst bleibt sie in einer ewigen Schleife (das wollen wir doch nicht, oder?).
2. Selbstaufruf: Hierbei ruft sich die Funktion selbst auf und geht immer tiefer, bis sie die Beendigungsbedingung erreicht.

Jetzt wollen wir sehen, wie das in der Praxis funktioniert!

Wie funktioniert es?

Um es besser zu erklären, gibt es nichts Besseres als das klassische Beispiel von Fakultät! Stellen Sie sich vor, wir möchten (5!) berechnen (sprich „fünf Fakultäten“). Wie funktioniert es?

5! = 5 * 4 * 3 * 2 * 1!

Mit der Rekursion können wir es uns jedoch so vorstellen:

5! = 5 * 4!

Und der Reihe nach ist 4! (4 * 3!) und so weiter, bis wir (1!) erreichen, was unser Basisfall (die Terminierung) ist Zustand).

Praxisbeispiel: Fakultät

Kommen wir zum Code, denn dort wird das Konzept zum Leben erweckt! Hier ist die berühmte faktorielle Berechnung mittels Rekursion:

def fatorial(numero):
    if numero == 0 or numero == 1:
        return 1  # caso base
    else:
        return numero * fatorial(numero - 1)

Erklärung:

1. Der Basisfall ist hier, wenn die Zahl 0 oder 1 ist, wobei die Funktion einfach 1 zurückgibt.
2. Wenn die Zahl größer als 1 ist, wird die Funktion mit der Zahl - 1 aufgerufen und die Werte bis zum Basisfall akkumuliert.

Komplexität

• Zeit: (O(n)) – da es n rekursive Aufrufe gibt.
• Leerzeichen: (O(n)) – Ausführungsstapeltiefe ist n.

Praxisbeispiel: Fibonacci

Ein weiteres weit verbreitetes Beispiel ist die Fibonacci-Folge. Sie ist so:

f(0) = 0, f(1) = 1, f(n) = f(n - 1) f(n - 2)

Kommen wir zum Code!

def seq_fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n > 1:
        return seq_fib(n - 1) + seq_fib(n - 2)

Fibonacci-Komplexität:

• Zeit: (O(2^n)) – exponentiell! ⚠️
• Leerzeichen: (O(n)) – Stapelnutzung für rekursive Aufrufe.

Deshalb kann die Fibonacci-Berechnung mit reiner Rekursion bei großen Werten etwas umständlich sein. Aber für Lernzwecke ist es ein tolles Beispiel!

Endlich

Rekursion ist ein Schlüsselkonzept in der Programmierung und obwohl es zunächst ein wenig einschüchternd wirken mag, wird es mit der Übung viel einfacher. Diese Fakultäts- und Fibonacci-Beispiele sind nur der Anfang!

Wenn Sie üben möchten, schauen Sie es sich an und machen Sie eine Kopie, in diesem Colab hier!

Das obige ist der detaillierte Inhalt vonRekursion in Python verstehen: Werden Sie sich damit auseinandersetzen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!