W tym artykule nauczysz się tworzyć funkcje rekurencyjne; funkcja, która sama siebie wywołuje. Dowiesz się również o rekurencyjnej funkcji ogona.
Funkcja, która wywołuje samą siebie, jest znana jako funkcja rekurencyjna. Ta technika jest znana jako rekurencja.
Przykładem świata fizycznego byłoby ustawienie dwóch równoległych luster naprzeciw siebie. Każdy obiekt pomiędzy nimi zostałby odzwierciedlony rekurencyjnie.
Jak działa rekursja w programowaniu?
fun main (args: Array) (… recurse ()…) fun recurse () (… recurse ()…)
Tutaj recurse()funkcja jest wywoływana z samej treści recurse()funkcji. Oto jak działa ten program:
Tutaj rekurencyjne wywołanie trwa wiecznie, powodując nieskończoną rekurencję.
Aby uniknąć nieskończonej rekurencji, można użyć if… else (lub podobnego podejścia), gdy jedna gałąź wykonuje wywołanie rekurencyjne, a inna nie.
Przykład: Znajdź silnię liczby przy użyciu rekursji
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) )
Po uruchomieniu programu wynik będzie następujący:
Silnia 4 = 24
Jak działa ten program?
Rekurencyjne wywołanie factorial()funkcji można wyjaśnić na poniższym rysunku:
Oto wymagane kroki:
silnia (4) // pierwsze wywołanie funkcji. Argument: 4 4 * silnia (3) // 2. wywołanie funkcji. Argument: 3 4 * (3 * silnia (2)) // 3. wywołanie funkcji. Argument: 2 4 * (3 * (2 * silnia (1))) // czwarte wywołanie funkcji. Argument: 1 4 * (3 * (2 * 1)) 24
Rekursja ogona Kotlina
Rekursja ogona jest pojęciem ogólnym, a nie cechą języka Kotlin. Niektóre języki programowania, w tym Kotlin, używają go do optymalizacji wywołań rekurencyjnych, podczas gdy inne języki (np. Python) ich nie obsługują.
Co to jest rekurencja ogona?
W normalnej rekurencji najpierw wykonujesz wszystkie wywołania rekurencyjne, a na końcu obliczasz wynik na podstawie zwracanych wartości (jak pokazano w powyższym przykładzie). W związku z tym nie otrzymasz wyniku, dopóki nie zostaną wykonane wszystkie wywołania rekurencyjne.
W przypadku rekurencji ogonowej najpierw wykonywane są obliczenia, a następnie wykonywane są wywołania rekurencyjne (wywołanie rekurencyjne przekazuje wynik bieżącego kroku do następnego wywołania rekurencyjnego). To sprawia, że rekurencyjne wywołanie jest równoważne zapętleniu i pozwala uniknąć ryzyka przepełnienia stosu.
Warunek rekurencji ogona
Funkcja rekurencyjna kwalifikuje się do rekurencji ogonowej, jeśli wywołanie jej samej jest ostatnią operacją, którą wykonuje. Na przykład,
Przykład 1: Nie kwalifikuje się do rekurencji ogonowej, ponieważ wywołanie funkcji do siebie n*factorial(n-1)nie jest ostatnią operacją.
fun silnia (n: Int): Long (if (n == 1) (return n.toLong ()) else (return n * silnia (n - 1)))
Przykład 2: kwalifikuje się do rekurencji ogonowej, ponieważ wywołanie funkcji do siebie fibonacci(n-1, a+b, a)jest ostatnią operacją.
fun fibonacci (n: Int, a: Long, b: Long): Long (return if (n == 0) b else fibonacci (n-1, a + b, a))
Aby nakazać kompilatorowi wykonanie rekurencji ogona w Kotlinie, musisz oznaczyć funkcję za pomocą tailrecmodyfikatora.
Przykład: rekurencja ogona
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) )
Po uruchomieniu programu wynik będzie następujący:
354224848179261915075
Ten program oblicza setny człon szeregu Fibonacciego. Ponieważ wynik może być bardzo dużą liczbą całkowitą, zaimportowaliśmy klasę BigInteger ze standardowej biblioteki Java.
Tutaj funkcja fibonacci()jest oznaczona tailrecmodyfikatorem, a funkcja kwalifikuje się do rekurencyjnego wywołania tail. Dlatego kompilator optymalizuje rekursję w tym przypadku.
Jeśli spróbujesz znaleźć 20000- ty człon (lub jakąkolwiek inną dużą liczbę całkowitą) z szeregu Fibonacciego bez użycia rekurencji ogona, kompilator zgłosi java.lang.StackOverflowErrorwyjątek. Jednak nasz program powyżej działa dobrze. Dzieje się tak dlatego, że użyliśmy rekurencji ogonowej, która używa wydajnej wersji opartej na pętli zamiast tradycyjnej rekurencji.
Przykład: silnia przy użyciu rekurencji ogona
Przykład obliczenia silni liczby w powyższym przykładzie (pierwszy przykład) nie może być zoptymalizowany pod kątem rekurencji ogonowej. Oto inny program do wykonania tego samego zadania.
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) )
Po uruchomieniu programu wynik będzie następujący:
Silnia 5 = 120
Kompilator może zoptymalizować rekursję w tym programie, ponieważ funkcja rekurencyjna kwalifikuje się do rekurencji ogona, a my użyliśmy tailrecmodyfikatora, który mówi kompilatorowi, aby zoptymalizował rekursję.
