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.