Odpowiedź.

Historia pytania

Rekurencja to przydatna technika, spotykana w językach funkcyjnych i w Kotlinie. Jednak bezpośrednia rekurencja często prowadzi do przepełnienia stosu (StackOverflowError). Aby temu zaradzić, wiele języków wprowadziło optymalizację rekurencji ogonowej (tail call optimization). W Kotlinie jest ona realizowana wyraźnie za pomocą słowa kluczowego tailrec.

Problem

Zwykła rekurencja tworzy nowe ramki stosu przy każdym wywołaniu. Kiedy głębokość rekurencji jest duża, prowadzi to do StackOverflowError. Automatyczna optymalizacja rekurencji ogonowej nie zawsze jest możliwa, a JVM nie obsługuje jej tak, jak na przykład kompilatory niektórych innych języków (Scala, Erlang).

Rozwiązanie

Kotlin pozwala oznaczyć funkcję słowem kluczowym tailrec. Jeśli funkcja rzeczywiście jest rekurencją ogonową ("tail call" — wynikowe wywołanie samej siebie jest ostatnią operacją), kompilator zamienia ją na pętlę, co eliminuje przepełnienie stosu.

Przykład kodu:

tailrec fun factorial(n: Int, acc: Int = 1): Int =
    if (n == 0) acc else factorial(n - 1, acc * n)

println(factorial(5)) // 120

Kluczowe cechy:

Funkcja musi być rekurencyjna, ostatnia operacja to wywołanie samej siebie
tailrec może być stosowane tylko do funkcji, które nie są open ani abstrakcyjne
Są ograniczenia: na przykład, nie można używać wewnątrz lambd ani gdy bezpośrednie wywołanie tail call jest zakryte przez inne operacje

Pytania z pułapką.

Co się stanie, jeśli tailrec jest używane, ale wywołanie nie znajduje się w pozycji ogonowej?

Kompilator zgłosi błąd i nie zastosuje optymalizacji.

tailrec fun sum(n: Int, acc: Int = 0): Int {
    println(n) // po tym nie można zoptymalizować
    return if (n == 0) acc else sum(n - 1, acc + n)
}
// Błąd kompilacji: wywołanie nie w pozycji ogonowej

Czy można używać tailrec w otwartych funkcjach lub metodach abstrakcyjnych?

Nie, słowo kluczowe działa tylko na funkcjach finalnych.

open class Base {
    // Błąd:
    // tailrec open fun test() {}
}

Czy jest różnica w wydajności między zwykłą rekurencją a tailrec?

Tak, tailrec przekształca funkcję w pętlę, zmniejszając koszty stosu i eliminując StackOverflowError.

Typowe błędy i antywzorce

Błędne użycie tailrec w pozycji nie-ogonowej, co prowadzi do błędu kompilacji
Próba użycia tailrec dla lambd lub funkcji o nietypowej strukturze return
Stosowanie tailrec tam, gdzie rekurencja jest trywialna i łatwiej zastąpić ją zwykłą pętlą

Przykład z życia

Negatywny przypadek

Programista oznacza wszystkie funkcje rekurencyjne jako tailrec, nie zadając sobie pytania, czy optymalizacja może być zastosowana. Wywołania nie zawsze znajdują się w pozycji ogonowej — ostatecznie projekty nie kompilują się, a rekurencja nie działa efektywnie.

Zalety:

Chęć uczynienia kodu optymalnym Wady:
Kompilacja przerywana, logika psuta, rekurencyjne wywołania mogą nie działać

Pozytywny przypadek

Programista analizuje logikę, implementuje rekurencję ogonową w funkcjach takich jak przeszukiwanie drzewa czy obliczanie silni. tailrec jest używane tam, gdzie to rzeczywiście możliwe. Powstaje efektywnie skompilowana pętla bez przepełnienia stosu.