In diesem Artikel lernen Sie, rekursive Funktionen zu erstellen. eine Funktion, die sich selbst aufruft. Außerdem lernen Sie die rekursive Funktion des Schwanzes kennen.
Eine Funktion, die sich selbst aufruft, wird als rekursive Funktion bezeichnet. Diese Technik wird als Rekursion bezeichnet.
Ein Beispiel für eine physikalische Welt wäre, zwei parallele Spiegel einander gegenüberzustellen. Jedes Objekt dazwischen würde rekursiv reflektiert.
Wie funktioniert die Rekursion in der Programmierung?
fun main (args: Array) (… recurse ()…) fun recurse () (… recurse ()…)
Hier wird die recurse()Funktion aus dem recurse()Funktionskörper selbst aufgerufen . So funktioniert dieses Programm:
Hier setzt sich der rekursive Aufruf für immer fort und verursacht eine unendliche Rekursion.
Um eine unendliche Rekursion zu vermeiden, kann … else (oder ein ähnlicher Ansatz) verwendet werden, wenn ein Zweig den rekursiven Aufruf ausführt und der andere nicht.
Beispiel: Finden Sie die Fakultät einer Zahl mithilfe der Rekursion
fun main(args: Array) ( val number = 4 val result: Long result = factorial(number) println("Factorial of $number = $result") ) fun factorial(n: Int): Long ( return if (n == 1) n.toLong() else n*factorial(n-1) )
Wenn Sie das Programm ausführen, lautet die Ausgabe wie folgt:
Faktor von 4 = 24
Wie funktioniert dieses Programm?
Der rekursive Aufruf der factorial()Funktion kann in der folgenden Abbildung erläutert werden:
Hier sind die Schritte:
Fakultät (4) // 1. Funktionsaufruf. Argument: 4 4 * Fakultät (3) // 2. Funktionsaufruf. Argument: 3 4 * (3 * Fakultät (2)) // 3. Funktionsaufruf. Argument: 2 4 * (3 * (2 * Fakultät (1))) // 4. Funktionsaufruf. Argument: 1 4 * (3 * (2 * 1)) 24
Kotlin Schwanz Rekursion
Die Schwanzrekursion ist eher ein allgemeines Konzept als das Merkmal der Kotlin-Sprache. Einige Programmiersprachen, einschließlich Kotlin, verwenden es, um rekursive Aufrufe zu optimieren, während andere Sprachen (z. B. Python) sie nicht unterstützen.
Was ist Schwanzrekursion?
Bei der normalen Rekursion führen Sie zuerst alle rekursiven Aufrufe aus und berechnen zuletzt das Ergebnis aus den Rückgabewerten (wie im obigen Beispiel gezeigt). Daher erhalten Sie kein Ergebnis, bis alle rekursiven Aufrufe getätigt wurden.
Bei der Endrekursion werden zuerst Berechnungen durchgeführt und dann rekursive Aufrufe ausgeführt (der rekursive Aufruf übergibt das Ergebnis Ihres aktuellen Schritts an den nächsten rekursiven Aufruf). Dies macht den rekursiven Aufruf gleichbedeutend mit einer Schleife und vermeidet das Risiko eines Stapelüberlaufs.
Bedingung für die Schwanzrekursion
Eine rekursive Funktion kann zur Schwanzrekursion verwendet werden, wenn der Funktionsaufruf für sich selbst die letzte von ihr ausgeführte Operation ist. Beispielsweise,
Beispiel 1: Nicht für die Schwanzrekursion geeignet, da der Funktionsaufruf für sich selbst n*factorial(n-1)nicht die letzte Operation ist.
Spaßfaktor (n: Int): Lang (if (n == 1) (return n.toLong ()) else (Rückgabe n * Fakultät (n - 1)))
Beispiel 2: Berechtigt zur Schwanzrekursion, da der Funktionsaufruf für sich selbst fibonacci(n-1, a+b, a)die letzte Operation ist.
lustige Fibonacci (n: Int, a: Long, b: Long): Long (Rückgabe, wenn (n == 0) b sonst Fibonacci (n-1, a + b, a))
Um den Compiler anzuweisen, eine Schwanzrekursion in Kotlin durchzuführen, müssen Sie die Funktion mit dem tailrecModifikator markieren .
Beispiel: Schwanzrekursion
import java.math.BigInteger fun main(args: Array) ( val n = 100 val first = BigInteger("0") val second = BigInteger("1") println(fibonacci(n, first, second)) ) tailrec fun fibonacci(n: Int, a: BigInteger, b: BigInteger): BigInteger ( return if (n == 0) a else fibonacci(n-1, b, a+b) )
Wenn Sie das Programm ausführen, lautet die Ausgabe wie folgt:
354224848179261915075
Dieses Programm berechnet das 100 - te Glied der Fibonacci - Reihe. Da die Ausgabe eine sehr große Ganzzahl sein kann, haben wir die BigInteger-Klasse aus der Java-Standardbibliothek importiert.
Hier ist die Funktion fibonacci()mit einem tailrecModifikator markiert und die Funktion kann rekursiv aufgerufen werden. Daher optimiert der Compiler in diesem Fall die Rekursion.
Wenn Sie versuchen , die 20000 zu finden th Begriff (oder jede andere große ganze Zahl) der Fibonacci - Reihe ohne Endrekursion zu verwenden, wird der Compiler wirft java.lang.StackOverflowErrorAusnahme. Unser obiges Programm funktioniert jedoch einwandfrei. Dies liegt daran, dass wir die Schwanzrekursion verwendet haben, bei der anstelle der herkömmlichen Rekursion eine effiziente schleifenbasierte Version verwendet wird.
Beispiel: Faktoriell mit Schwanzrekursion
Das Beispiel zur Berechnung der Fakultät einer Zahl im obigen Beispiel (erstes Beispiel) kann nicht für die Schwanzrekursion optimiert werden. Hier ist ein anderes Programm, um dieselbe Aufgabe auszuführen.
fun main(args: Array) ( val number = 5 println("Factorial of $number = $(factorial(number))") ) tailrec fun factorial(n: Int, run: Int = 1): Long ( return if (n == 1) run.toLong() else factorial(n-1, run*n) )
Wenn Sie das Programm ausführen, lautet die Ausgabe wie folgt:
Faktor 5 = 120
Der Compiler kann die Rekursion in diesem Programm optimieren, da die rekursive Funktion für die Endrekursion geeignet ist. Wir haben einen tailrecModifikator verwendet, der den Compiler anweist, die Rekursion zu optimieren.
