Rekurencja ogonkowa w Kotlinie
Na początek kilka słów na temat terminów.
Rekurencja
Jest sobie definicja w wikipediiW. Można ją uprościć do:
Jeżeli funkcja odwołuje się do samej siebie to jest rekurencyjna
Co do zasady w programach mamy rekurencję skończoną. Chyba że założenie o nieskończoności jest ok, a nasz język nie będzie miał problemu z przepełnieniem stosu w wyniku nieskończonej ilości wywołań. Rekurencja skończona, poza wywołaniem funkcji przez samą siebie, ma też warunek stopu, czyli miejsce gdzie stos wywołań zaczyna „się zwijać”.
Rekurencja ogonkowa
Jest to specjalna forma rekurencji gdzie ostatnim wywołaniem jest:
- Wywołanie związane z warunkiem stopu, albo
- wywołanie rekurencyjne.
Tu czyha pułapka, którą można zilustrować w następujący sposób:
Listing 1. Rekurencja udająca ogonkową
fun fac(i: Int): Int {
if (i == 0)
return 1;
return i * fac(i - 1);
}
Gdy czytamy powyższy kod „wydaje się”, że wywołanie fun jest ostatnim. Jednak w rzeczywistości po tym wywołaniu następuje jeszcze mnożenie. Ot taki mały myk.
Rekurencja ogonkowa ma to do siebie, że może zostać zamieniona na iteracją. A skoro tak…
Funkcje tailrec
Zamiana na iterację jest prosta. Można jej dokonać automatycznie. W Kotlinie oznacza, to iż kompilator może wygenerować odpowiednią optymalizację. W tym celu należy użyć słowa kluczowego tailrec:
Listing 2. Przykład użycia tailrec
fun main(args: Array<String>) {
println(fac(BigInteger.valueOf(20000L)))
}
fun fac(i: BigInteger): BigInteger {
tailrec fun internalFac(acc: BigInteger, elem: BigInteger): BigInteger {
if (elem.equals(BigInteger.ZERO))
return acc;
return internalFac(acc * elem, elem - BigInteger.ONE)
}
return internalFac(BigInteger.ONE, i);
}
Policzy i się nie wywali. Jak usuniemy tailrec, oczywiście otrzymamy SOE. BTW:
Listing 3. Przykład użycia tailrec dla rekurencji nie ogonkowej
tailrec fun fac(i: Int): Int {
if (i == 0)
return 1;
return i * fac(i - 1);
}
choć kod jest nieprawidłowy, to nie zostaniemy o tym poinformowani. Szkoda.
Podsumowanie
Kotlin pozwala na deklarowanie funkcji, które są rekurencyjne, a gdy stworzymy funkcję ogonkową, to kompilator będzie umiał zaaplikować odpowiednie optymalizacje.