tailrec în Kotlin

tailrec fun nume(param: Tip, acumulator: Tip): Tip =
    if (gata) acumulator else nume(paramNou, acumulatorNou)

Ce face tailrec

O funcție recursivă se apelează pe ea însăși. Fiecare apel ocupă loc pe stivă, iar la zeci de mii de apeluri programul se oprește cu StackOverflowError. Dacă apelul recursiv este ultima operație a funcției (recursivitate de coadă), Kotlin o poate transforma într-o buclă: marchezi funcția cu tailrec.

Condiția este strictă: după apelul recursiv nu trebuie să mai urmeze nimic. n * factorial(n - 1) nu este de coadă (înmulțirea vine după apel); se rescrie cu un parametru acumulator: factorial(n - 1, acc * n). Dacă funcția nu respectă condiția, compilatorul avertizează (a function is marked as tail-recursive but no tail calls are found). Apelul nu poate sta nici într-un try.

Exemple

Exemplul 1: Factorial cu acumulator

Ultimul lucru din funcție este apelul factorial(n - 1, acc * n), deci tailrec se aplică.

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

fun main() {
    println("5! = ${factorial(5)}")
    println("10! = ${factorial(10)}")
    println("20! = ${factorial(20)}")
}

Rezultat

5! = 120
10! = 3628800
20! = 2432902008176640000

Exemplul 2: Cel mai mare divizor comun (Euclid)

Algoritmul lui Euclid este natural de coadă: răspunsul este apelul recursiv însuși.

tailrec fun cmmdc(a: Int, b: Int): Int = if (b == 0) a else cmmdc(b, a % b)

fun main() {
    println("cmmdc(48, 18) = ${cmmdc(48, 18)}")
    println("cmmdc(1071, 462) = ${cmmdc(1071, 462)}")
    val numarator = 84
    val numitor = 126
    val d = cmmdc(numarator, numitor)
    println("$numarator/$numitor = ${numarator / d}/${numitor / d}")
}

Rezultat

cmmdc(48, 18) = 6
cmmdc(1071, 462) = 21
84/126 = 2/3

Exemplul 3: Un milion de pași fără StackOverflowError

Fără tailrec, un milion de apeluri recursive ar umple stiva. Cu tailrec funcția rulează ca o buclă.

tailrec fun sumaPanaLa(n: Long, acc: Long = 0): Long =
    if (n == 0L) acc else sumaPanaLa(n - 1, acc + n)

fun main() {
    println(sumaPanaLa(100))
    println(sumaPanaLa(1_000_000))
}

Rezultat

5050
500000500000

Greșeli frecvente

• tailrec fun f(n: Int): Int = if (n == 0) 0 else n + f(n - 1): adunarea se face după apel, deci nu e recursivitate de coadă. Compilatorul avertizează, iar funcția rămâne recursivă normal.
• Credința că tailrec face orice recursivitate sigură: recursivitatea pe arbori (două apeluri, stânga și dreapta) nu poate fi de coadă.
• Funcții tailrec care pot fi suprascrise (open): nu sunt permise.

Comenzi înrudite

• fun: fun declară o funcție: un bloc de cod cu nume, care primește parametri și poate returna un rezultat.
• while și do-while: while repetă un bloc cât timp condiția e adevărată; do-while execută blocul o dată, apoi verifică condiția.
• return: Încheie funcția curentă și întoarce o valoare apelantului; cu etichetă (return@forEach) iese doar din lambda.