Python Tutorial - Rekursive Funktion

1. Was ist eine Python-Rekursivfunktion
2. Begrenzung der Rekursion
3. Vorteil der Rekursion
4. Nachteil der Rekursion

In diesem Abschnitt lernen Sie die rekursive Funktion von Python kennen.

Was ist eine Python-Rekursivfunktion

Eine rekursive Funktion ist eine Funktion, die sich selbst aufruft und dieser Vorgang wird Funktionsrekursion genannt.

Berechnen wir zum Beispiel die Fakultät einer Zahl, zum Beispiel 6.

6 * 5 * 4 * 3 * 2 * 1

Im folgenden Code wird eine rekursive Funktion erstellt, die die Fakultät einer Zahl findet:

def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)


a = 6
print("Factorial of", a, "=", fact(a))

Factorial of 6 = 720

Die Funktion fact(n) ist eine rekursive Funktion. Die Funktion fact ruft sich selbst mit dem Argument n-1 auf, bis die Zahl 1 wird, und so wird die Fakultät berechnet, d.h. die Zahl wird mit der Fakultät von eins weniger als der Zahl multipliziert.

In dieser rekursiven Funktion gibt es eine Grundbedingung, die ist, wenn die Zahl 1 wird, 1 zurückgegeben wird und auf diese Weise der rekursive Aufruf endlich wird.

Wenn eine rekursive Funktion erstellt wird, muss es eine Basisbedingung geben, um diesen rekursiven Aufruf zu beenden.

Begrenzung der Rekursion

Wie Sie bemerkt haben, benötigt die Funktion jedes Mal, wenn sie sich selbst aufruft, etwas Speicherplatz, um einige Zwischenwerte zu speichern. Deshalb verbraucht eine rekursive Funktion viel mehr Speicher als eine normale nicht rekursive Funktion. Python setzt die Begrenzung der Rekursionsaufrufe auf 3000.

>>> import sys
>>> sys.getrecursionlimit()
3000

Es löst einen RecursionError aus, wenn die Rekursion 3000 überschreitet.

def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)


print(fact(4000))

Traceback (most recent call last):
  File "<pyshell#2>", line 1, in <module>
    print(factorial(4000))
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  [Previous line repeated 989 more times]
  File "<pyshell#1>", line 2, in factorial
    if n == 1:
RecursionError: maximum recursion depth exceeded in comparison

Lösung zum Entfernen der Rekursionsbeschränkung

Sie könnten die Rekursionsbegrenzung lösen, indem Sie die Rekursionsbegrenzung auf eine Zahl größer als die gewünschte Rekursion setzen.

import sys

sys.setrecursionlimit(5000)


def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)


print(fact(4000))

Vorteil der Rekursion

• Mit Hilfe rekursiver Funktionen kann das Problem in Teilprobleme unterteilt werden, die sich leicht lösen lassen.
• Der Code wird sauber und übersichtlich.

Nachteil der Rekursion

• Es ist manchmal schwierig, die Logik der rekursiven Funktion zu durchschauen.
• Jedes Teilproblem zu lösen wird viel Zeit in Anspruch nehmen, so dass rekursive Funktionen ineffizient sind.