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.

2 myśli na temat “Rekurencja ogonkowa w Kotlinie

  1. Co do nieskończonych funkcji rekurencyjnych. Można bez problemu pisać główne pętle serwerów czy demonów w sposób rekurencyjny, oczywiście używając rekurencji ogonowej.

    @tailrec w scali jednak rzuca błędem przy przy tym, chociaż sądzę że to jest po prostu więcej czasu dla kompilatora by zgłaszał błąd.

  2. Warto wiedzieć, że ta optymalizacja to najprawdopodobniej zamiana na pętlę. Tak jest przynajmniej w Scali. JVM nie optymalizuje rekurencji ogonkowej (choć jest to w planach), więc musi robić to kompilator.

Napisz odpowiedź

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax