Personen mit Programmiererfahrung müssen mit rekursiven Funktionen vertraut sein. Rekursive Algorithmen sind für die meisten Probleme sehr effektiv und können auch unseren Code optimieren bei Verwendung von Rekursion:
1) Rekursion ruft die Funktion selbst innerhalb der Funktion selbst auf.
2) Die Effizienz der Rekursion ist relativ gering und es wird nicht empfohlen, sie zu verwenden, wenn eine zeitliche Begrenzung besteht.
3) Im rekursiven Prozess muss eine klare Endbedingung vorhanden sein, dh der rekursive Ausgang.
Lassen Sie uns die rekursiven Funktionen im Folgenden ausführlich erläutern.
Schauen wir uns zunächst die einfache Verwendung der Rekursion anhand eines Beispiels an:
m=int(input('Geben Sie eine Zahl ein:'))deftest(x):x+=2ifx<100:test(x)else:print('Das letzte x ist:',x)test(m)Die Ausgabe ist:
Geben Sie eine Zahl ein: 20 und das letzte x ist: 100
Lassen Sie uns dieses Beispiel analysieren. In der ersten Zeile des Codes wird m als tatsächlicher Parameter an die test()-Methode übergeben 2 Zuerst und dann Eine Beurteilung: Wenn der Wert von x kleiner als 100 ist, rufen Sie diese Funktion erneut auf. Beim Aufruf wird der aktuelle Wert von x als tatsächlicher Parameter verwendet, um am Aufruf teilzunehmen. Die Rekursion endet, wenn x> =100 ist erfüllt.
Schauen Sie sich das Diagramm unten an:
Das heißt, wenn die Bedingungen nicht erfüllt sind, kehrt es zur äußersten Ebene zurück und ruft diese Funktion auf.
Wenn es um klassische Probleme in rekursiven Algorithmen geht, sind die Fibonacci-Folge und der Turm von Hanoi immer untrennbar miteinander verbunden. Hier erklären wir, wie man die Fibonacci-Folge mithilfe der Rekursion löst.
Zunächst müssen wir wissen, dass die rekursive Formel der Fibonacci-Folge F(n)=F(n-1)+F(n-2) ist, F(1) und F(2) 1 sind kann Rekursion verwenden, um den Wert eines Elements in der Fibonacci-Folge zu ermitteln.
Es gibt viele Möglichkeiten, Fibonacci-Folgenprobleme zu lösen.
Zuerst verwenden wir die häufig verwendete rekursive Methode, um dieses Problem zu lösen:
N=int(input(geben Sie die Anzahl der zu erhaltenden Elemente ein:))deffibonacci(n):ifn<=2:#Wenn es kleiner oder gleich 2 ist, setzen Sie n auf 1 return1else:returnfibonacci(n-1) +fibonacci(n-2)print ('Der entsprechende Wert ist',fibonacci(n))Die Ausgabe ist:
Geben Sie die Anzahl der Artikel ein, die Sie erhalten möchten: 4 entspricht 3
Wenn wir für diese rekursive Aufrufmethode den Wert 4 eingeben, werden die folgenden Operationen rekursiv ausgeführt:
Fibonacci(3)+Fibonacci(2)=Fibonacci(2)+Fibonacci(1)+Fibonacci(2)
Dann können wir sehen, dass der Wert des vierten Termes 1+1+1=3 ist.
Tatsächlich ist diese Lösungsmethode Zeitverschwendung, da zu viele Iterationen erforderlich sind. Wir können zur Lösung dieses Problems auch Platz anstelle von Zeit verwenden.
Der Code lautet wie folgt:
n=int(input(geben Sie die Anzahl der zu erhaltenden Terme ein:))fibonacci=[1,1]foriinrange(2,n):fibonacci.append(fibonacci[i-1]+fibonacci[i-2])print ('Der entsprechende Wert ist',fibonacci[n-1])Die Ausgabe ist:
Geben Sie die Anzahl der Artikel ein, die Sie erhalten möchten: 4 entspricht 3
Auf diese Weise geben wir zunächst die Werte der ersten beiden Elemente in der Liste an und füllen dann für die Anzahl n der Elemente, die wir lösen möchten, die Liste der Fibonacci-Zahlen direkt über die Formel mit dem Element, das wir benötigen. und schließlich entsprechend dem Index Der Wert findet direkt das entsprechende Ausgabeergebnis.
Das ist alles für die rekursive Funktion. Wie oben erwähnt, sollten wir dem rekursiven Exit und den Zeitlimits besondere Aufmerksamkeit schenken. Der Exit ist der Schlüssel zum Ende der Rekursion Wenn wir die angegebene Zeit überschreiten, müssen wir zu diesem Zeitpunkt unsere Denkweise ändern, um das Problem zu lösen.