Functions and recursion - Learn Python 3 - Snakify

Lesson 8
Funktionen und Rekursion


1. Funktionen

Erinnern Sie sich daran, dass in der Mathematik die Fakultät einer Zahl n als n definiert ist ! = 1 ⋅ 2 ⋅ ... ⋅ n (als Produkt aller ganzen Zahlen von 1 bis n). Zum Beispiel 5! = 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 = 120. Es ist klar, dass faktoriell mit einer for-Schleife einfach zu berechnen ist. Stellen Sie sich vor, dass wir in unserem Programm die Fakultät verschiedener Zahlen mehrmals (oder an verschiedenen Stellen des Codes) berechnen müssen. Natürlich können Sie die Berechnung der Fakultät einmal schreiben und dann mit Kopieren-Einfügen einfügen, wo Sie sie brauchen:

# berechne 3!
res = 1
for i in range(1, 4):
    res *= i
print(res)

# berechne 5!
res = 1
for i in range(1, 6):
    res *= i
print(res)

Wenn wir jedoch im ursprünglichen Code einen Fehler machen, wird dieser fehlerhafte Code an allen Stellen angezeigt, an denen wir die Berechnung der Fakultät kopiert haben. Außerdem ist der Code länger als er sein könnte. Um das Umschreiben derselben Logik in Programmiersprachen zu vermeiden, gibt es Funktionen.

Funktionen sind die Codeabschnitte, die vom Rest des Programms isoliert sind und nur ausgeführt werden, wenn sie aufgerufen werden. Sie haben die Funktion sqrt() , len() und print() bereits erfüllt. Sie alle haben etwas gemeinsam: Sie können Parameter nehmen (null, eins oder mehrere), und sie können einen Wert zurückgeben (obwohl sie möglicherweise nicht zurückkehren). Zum Beispiel akzeptiert die Funktion sqrt() einen Parameter und gibt einen Wert zurück (die Quadratwurzel der gegebenen Zahl). Die Funktion print() kann verschiedene Argumente annehmen und gibt nichts zurück.

Jetzt wollen wir Ihnen zeigen, wie man eine Funktion namens factorial() schreibt, die einen einzigen Parameter - die Zahl - verwendet und einen Wert zurückgibt - die Fakultät dieser Zahl.

def factorial(n):
    res = 1
    for i in range(1, n + 1):
        res *= i
    return res

print(factorial(3))
print(factorial(5))

Wir möchten ein paar Erklärungen geben. Zuerst sollte der Funktionscode am Anfang des Programms stehen (vor dem Ort, an dem wir die Funktion factorial() , um genau zu sein). Die erste Zeile def factorial(n): dieses Beispiels ist eine Beschreibung unserer Funktion; Das Wort faktoriell ist ein Bezeichner (der Name unserer Funktion). Gleich nach dem Bezeichner folgt die Liste der Parameter, die unsere Funktion empfängt (in Klammern). Die Liste besteht aus durch Komma getrennten Identifikatoren der Parameter; In unserem Fall besteht die Liste aus einem Parameter n . Am Ende der Zeile, legen Sie einen Doppelpunkt.

Dann geht der Funktionskörper. In Python muss der Text eingerückt sein (wie üblich durch Tab oder vier Leerzeichen). Diese Funktion berechnet den Wert von n! und speichert es in der Variablen res . Die letzte Zeile der Funktion ist return res , die die Funktion verlässt und den Wert der Variablen res zurückgibt.

Die return Anweisung kann an jeder Stelle einer Funktion erscheinen. Die Ausführung beendet die Funktion und gibt den angegebenen Wert an die Stelle zurück, an der die Funktion aufgerufen wurde. Wenn die Funktion keinen Wert zurückgibt, gibt die Rückgabeanweisung tatsächlich keinen Wert zurück (obwohl sie immer noch verwendet werden kann). Einige Funktionen müssen keine Werte zurückgeben, und die return-Anweisung kann für sie weggelassen werden.

Wir möchten ein anderes Beispiel geben. Hier ist die Funktion max() , die zwei Zahlen akzeptiert und das Maximum von ihnen zurückgibt (tatsächlich ist diese Funktion bereits Teil der Python-Syntax geworden).

def max(a, b):
    if a > b:
        return a
    else:
        return b

print(max(3, 5))
print(max(5, 3))
print(max(int(input()), int(input())))

Jetzt können Sie eine Funktion max3() schreiben, die drei Zahlen benötigt und deren Maximum zurückgibt.

def max(a, b):
    if a > b:
        return a
    else:
        return b

def max3(a, b, c):
    return max(max(a, b), c)

print(max3(3, 5, 4))

Die eingebaute Funktion max() in Python kann verschiedene Anzahl von Argumenten akzeptieren und das Maximum von ihnen zurückgeben. Hier ist ein Beispiel, wie eine solche Funktion geschrieben werden kann.

def max(*a):
    res = a[0]
    for val in a[1:]:
        if val > res:
            res = val
    return res

print(max(3, 5, 4))
Alles, was an diese Funktion übergeben wird, sammelt die Parameter in einem einzelnen Tupel namens a , das durch das Sternchen gekennzeichnet ist.
Advertising by Google, may be based on your interests

2. Lokale und globale Variablen

Innerhalb der Funktion können Sie Variablen verwenden, die irgendwo außerhalb davon deklariert sind:

def f():
    print(a)

a = 1
f()

Hier wird die Variable a auf 1 gesetzt, und die Funktion f() diesen Wert aus, obwohl diese Variable bei der Deklaration der Funktion f nicht initialisiert wird. Der Grund dafür ist, zum Zeitpunkt des Aufrufs der Funktion f() (die letzte Zeichenfolge) die Variablen a bereits einen Wert hat. Deshalb kann die Funktion f() sie anzeigen.

Solche Variablen (außerhalb der Funktion deklariert, aber innerhalb der Funktion verfügbar) werden global genannt .

Wenn Sie jedoch eine Variable innerhalb der Funktion initialisieren, können Sie diese Variable nicht außerhalb dieser Funktion verwenden. Beispielsweise:

def f():
    a = 1

f()
print(a)

Wir erhalten Fehler NameError: name 'a' is not defined . Solche innerhalb einer Funktion deklarierten Variablen heißen lokal . Sie sind nach dem Beenden der Funktion nicht mehr verfügbar.

Was wirklich reizvoll ist, passiert, wenn Sie den Wert einer globalen Variablen innerhalb einer Funktion ändern:

def f():
    a = 1
    print(a)

a = 0
f()
print(a)

Dieses Programm druckt man die Zahlen 1 und 0. Trotz der Tatsache , dass der Wert der Variablen a in der Funktion verändert, außerhalb der Funktion es gleich bleibt! Dies geschieht, um globale Variablen vor unbeabsichtigten Funktionsänderungen zu schützen. Wenn also eine Variable innerhalb der Funktion geändert wird, wird die Variable zu einer lokalen Variablen, und ihre Änderung ändert keine globale Variable mit demselben Namen.

Formaler: Der Python-Interpreter betrachtet eine Variable als lokal für die Funktion, wenn im Code dieser Funktion mindestens eine Anweisung vorhanden ist, die den Wert der Variablen ändert. Dann kann diese Variable auch nicht vor der Initialisierung verwendet werden. Anweisungen, die den Wert einer Variablen ändern - die Operatoren = , += und die Verwendung der Variablen als Schleife for Parameter. Aber selbst wenn die Anweisung mit wechselnden Variablen nie ausgeführt wird, kann der Interpreter sie nicht überprüfen, und die Variable ist immer noch lokal. Ein Beispiel:

def f():
    print(a)
    if False:
        a = 0

a = 1
f()

Ein Fehler tritt auf: UnboundLocalError: local variable 'a' referenced before assignment . In der Funktion f() der Bezeichner a eine lokale Variable, da die Funktion den Befehl enthält, der die Variable a modifiziert. Die modifizierende Anweisung wird niemals ausgeführt, aber der Interpreter wird sie nicht prüfen. Wenn Sie also versuchen, die Variable a zu drucken, sprechen Sie eine nicht initialisierte lokale Variable an.

Wenn Sie möchten, dass eine Funktion eine Variable ändern kann, müssen Sie diese Variable innerhalb der Funktion mit dem Schlüsselwort global deklarieren:

def f():
    global a
    a = 1
    print(a)

a = 0
f()
print(a)

In diesem Beispiel wird die Ausgabe von 1 1 ausgegeben, da die Variable a als global deklariert ist und wenn sie innerhalb der Funktion geändert wird, wird sie global geändert.

Es ist jedoch besser, Werte globaler Variablen in einer Funktion nicht zu ändern. Wenn Ihre Funktion muss eine Variable ändern, lassen Sie es diesen Wert zurück, und Sie wählen , wenn die Funktion explizit zuweisen eine Variable auf diesen Wert aufrufen. Wenn Sie diese Regeln befolgen, funktioniert die Logik der Funktionen unabhängig von der Code-Logik, und somit können solche Funktionen leicht von einem Programm in ein anderes Programm kopiert werden, was Zeit spart.

Angenommen, Ihr Programm sollte die Fakultät der angegebenen Zahl berechnen, die Sie in der Variablen f speichern möchten. Hier ist, wie Sie es nicht tun sollten :

def factorial(n):
    global f
    res = 1
    for i in range(2, n + 1):
        res *= i
    f = res

n = int(input())
factorial(n)
print(f)
# andere Sachen mit der Variablen f machen

Dies ist das Beispiel für schlechten Code, da es schwierig ist, einen anderen Zeitpunkt zu verwenden. Wenn Sie morgen ein anderes Programm benötigen, um die Funktion "faktoriell" zu verwenden, können Sie diese Funktion nicht einfach von hier kopieren und Ihr neues Programm einfügen. Sie müssen sicherstellen, dass dieses Programm nicht die Variable f .

Es ist viel besser, dieses Beispiel wie folgt neu zu schreiben:

# Start eines Teils des Codes, der von Programm zu Programm kopiert werden kann
def factorial(n):
    res = 1
    for i in range(2, n + 1):
        res *= i
    return res
# Ende des Stückes Code

n = int(input())
f = factorial(n)
print(f)
# andere Sachen mit der Variablen f machen

Es ist nützlich zu sagen, dass Funktionen mehr als einen Wert zurückgeben können. Hier ist ein Beispiel für die Rückgabe einer Liste mit zwei oder mehr Werten:

return [a, b]

Sie können die Funktion einer solchen Liste aufrufen und in mehrfacher Zuordnung verwenden:

n, m = f(a, b)
Advertising by Google, may be based on your interests

3. Rekursion

Wie wir oben gesehen haben, kann eine Funktion eine andere Funktion aufrufen. Aber Funktionen können sich auch selbst anrufen! Betrachten Sie zur Veranschaulichung das Beispiel der faktoriellen Rechenfunktion. Es ist bekannt, dass 0! = 1, 1! = 1. Wie berechnet man den Wert von n! für große n? Wenn wir den Wert von (n-1)! Berechnen könnten, dann berechnen wir leicht n!, Da n! = N⋅ (n-1) !. Aber wie berechnet man (n-1) !? Wenn wir (n-2)! Berechnet haben, dann ist (n-1)! = (N-1) ⋅ (n-2)!). Wie berechnet man (n-2) !? Wenn ... Am Ende kommen wir zu 0 !, was gleich 1 ist. Somit können wir zur Berechnung der Fakultät den Wert der Fakultät für eine kleinere ganze Zahl verwenden. Diese Berechnung kann mit Python durchgeführt werden:

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

print(factorial(5))        

Die Situation, wenn die Funktion sich selbst aufruft, wird Rekursion genannt , und diese Funktion wird rekursiv genannt.

Rekursive Funktionen sind ein mächtiger Mechanismus beim Programmieren. Leider sind sie nicht immer effektiv und führen oft zu Fehlern. Der häufigste Fehler ist die unendliche Rekursion , wenn die Kette von Funktionsaufrufen nie endet (naja, eigentlich endet sie, wenn der freie Speicher auf Ihrem Computer aufgebraucht ist). Ein Beispiel für unendliche Rekursion:

def f():
    return f()
Die zwei häufigsten Gründe für eine unendliche Rekursion:
  1. Falsche Abbruchbedingung. Wenn zum Beispiel im faktoriellen Berechnungsprogramm vergessen wird, die Überprüfung if n == 0 , if n == 0 , dann wird factorial(0) factorial(-1) aufrufen, was factorial(-2) usw. factorial(-2) wird.
  2. Rekursiver Aufruf mit falschen Parametern. Wenn zum Beispiel die Funktion factorial(n) die Funktion aufruft factorial(n) , werden wir auch eine unendliche Kette von Anrufen erhalten.

Beim Kodieren einer rekursiven Funktion muss daher zuerst sichergestellt werden, dass sie ihre Stoppbedingungen erreicht - um zu überlegen, warum Ihre Rekursion jemals enden wird.

Advertising by Google, may be based on your interests
Advertising by Google, may be based on your interests