Kotlin Rekursion und Schritteinkopplung

In diesem Artikel werden Sie lernen, rekursive Funktionen zu erstellen. Eine selbstaufrufende Funktion. Darüber hinaus werden Sie die tailrekursiven Funktionen kennenlernen.

aufruft sich selbstFunktionDiese Funktion wird als rekursiv bezeichnet. Und diese Technik wird als Rekursion bezeichnet.

Ein Beispiel aus der physischen Welt ist die relative Anordnung von zwei parallelen Spiegeln. Jeglicher Gegenstand zwischen ihnen wird rekursiv reflektiert.

Wie funktioniert Rekursion in der Programmierung?

fun main(args: Array<String>) {
　　　　... .. ...
　　　　recurse()
　　　　... .. ...
}
fun recurse() {
　　　　... .. ...
　　　　recurse()
　　　　... .. ...
}

Hier wird die Funktion recurse() aus dem Hauptteil der Funktion recurse() selbst aufgerufen. Der Arbeitsmechanismus dieses Programms ist wie folgt:

Hier führt der Rekursionsaufruf ständig weiter, was zu einer unendlichen Rekursion führt.

Um unendliche Rekursion zu vermeiden, kann in einem Zweig rekursiv aufgerufen werden, während in anderen Zweigen nicht rekursiv aufgerufen wird.if ... elseoder ähnliche Methoden).

Beispiel: Verwenden Sie Rekursion, um die Fakultät einer Zahl zu finden

fun main(args: Array<String>) {
　　　　val　number　=　4
　　　　val result: Long
　　　　result = factorial(number)
　　　　println("$number Fakultät = $result")
}
fun factorial(n: Int): Long {
　　　　return　if　(n　==　1) n.toLong() else n*factorial(n-1)
}

Wenn das Programm ausgeführt wird, lautet die Ausgabe:

4　Fakultät =　24

Wie funktioniert dieses Programm?

Das Diagramm von factorial() zeigt die rekursiven Aufrufe dieser Funktion an:

Die folgenden Schritte sind beteiligt:

factorial(4)　　　　　　　　　　　　　　//　der1der nächste Funktionsaufruf, Parameter:　4
4*factorial(3)　　　　　　　　　　　　//　der2der nächste Funktionsaufruf, Parameter:　3
4*(3*factorial(2))　　　　　　　　//　der3der nächste Funktionsaufruf, Parameter:　2
4*(3*(2*factorial(1))　　　　//　der4der nächste Funktionsaufruf, Parameter:　1　
4*(3*(2*1))　　　　　　　　　　　　　　　　　
24

Kotlin tailrekursiv

Tailrekursiv ist keine Eigenschaft der Kotlin-Sprache, sondern ein allgemeiner Begriff. Einige Programmiersprachen, einschließlich Kotlin, nutzen ihn, um Rekursionsaufrufe zu optimieren, während andere Sprachen (z.B. Python) sie nicht unterstützen.

Was ist tailrekursiv?

Bei der normalen Rekursion werden zunächst alle Rekursionsaufrufe ausgeführt und das Ergebnis am Ende auf Basis der Rückgabewerte berechnet (wie im obigen Beispiel gezeigt). Daher erhalten Sie vor dem Ausführen aller Rekursionsaufrufe keine Ergebnisse.

In der tailrekursiven Rekursion wird zunächst der Berechnung ausgeführt, dann die Rekursionsaufrufe (der Rekursionsaufruf gibt das aktuelle Ergebnis an den nächsten Rekursionsaufruf weiter). Dies macht den Rekursionsaufruf gleichwertig mit einer Schleife und vermeidet das Risiko von Stack Overflow.

Bedingungen für die tailrekursiv

Wenn die Selbstaufrufe der Funktion der letzte Operation sind, die sie ausführt, kann diese rekursive Funktion tailrekursiv sein. Zum Beispiel,

Beispiel1:n}} nicht die Bedingung der nachfolgenden Rekursion erfüllt, weil die nachfolgende Funktion auf sich selbst n*factorial(n-1) ist nicht die letzte Operation.

fun factorial(n: Int): Long {
　　　　if (n ==　1) {
　　　　　　　　return n.toLong()
　　　　} else {
　　　　　　　　return n*factorial(n　-　1)　　　　　
　　　　}
}

Beispiel2:erfüllt die Bedingung der nachfolgenden Rekursion, weil die nachfolgende Funktion auf sich selbst fibonacci(n-1, a+b, a) ist die letzte Operation.

fun fibonacci(n: Int, a: Long, b: Long): Long {
　　　　return if (n == 0) b else fibonacci(n-1, a+, b, a)
}

Um dem Compiler zu sagen, dass nachfolgende Rekursion in Kotlin ausgeführt wird, müssen Sie den Funktion den tailrec-Bezeichner markieren.

Beispiel: Nachfolgende Rekursion

import java.math.BigInteger
fun main(args: Array<String>) {
　　　　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 das Programm ausgeführt wird, lautet die Ausgabe:

354224848179261915075

Dieser Programm berechnet die n-te Fibonacci-Zahl der Fibonacci-Reihe100 Artikel. Da die Ausgabe sehr große Ganzzahlen sein kann, haben wir die BigInteger-Klasse aus der Java-Standardbibliothek importiert.

Hier wird die Funktion fibonacci() mit dem trarec-Bezeichner markiert, die berechtigt ist, nachfolgende Rekursion aufzurufen. Daher optimiert der Compiler die Rekursion in diesem Fall.

Wenn Sie versuchen, die n-te Fibonacci-Zahl ohne nachfolgende Rekursion zu finden20000 Artikel (oder jede andere große Zahl), der Compiler wirft java.lang.StackOverflowError Ausnahme.
Aber unser Programm läuft gut. Dies liegt daran, dass wir nachfolgende Rekursion verwendet haben, die eine effiziente auf Basis der Schleife Version verwendet, anstatt der traditionellen Rekursion.

Beispiel: Faktorial mit nachfolgender Rekursion

Der obige Beispiel (erster Beispiel) verwendet, um die numerische Potenzfunktion zu berechnen, kann nicht optimiert werden, um die nachfolgende Rekursion. Dies ist eine andere Programm, das denselben Task ausführt.

fun main(args: Array<String>) {
　　　　val　number　=　5
　　　　println("$number　Fakultät　=　${factorial(number)}")
}
tailrec　fun　factorial(n:　Int,　run:　Int　=　1):　Long　{
　　　　return　if　(n　==　1)　run.toLong()　else　factorial(n-1,　run*n)
}

Wenn das Programm ausgeführt wird, lautet die Ausgabe:

5　Fakultät=　120

Der Compiler kann die Rekursion in diesem Programm optimieren, da rekursive Funktionen Schritteinkopplung durchführen können und wir den tailrec-Modifikator verwenden, um dem Compiler zu sagen, dass die Rekursion optimiert werden soll.