دوال tailrec

ما الاستدعاء الذاتي النهائي؟

tailrec fun countdown(n: Int) {
    if (n < 0) return
    println(n)
    countdown(n - 1)
}

fun main() {
    countdown(3)
}

معدِّل tailrec

tailrec fun sum(n: Int, acc: Int = 0): Int {
    if (n == 0) return acc
    return sum(n - 1, acc + n)
}

fun main() {
    println(sum(100))
}

نمط المُجمِّع

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

fun main() {
    println(factorial(10))
}

لماذا يجب أن يكون الاستدعاء أخيرًا؟

tailrec fun length(s: String, acc: Int = 0): Int {
    if (s.isEmpty()) return acc
    return length(s.drop(1), acc + 1)
}

fun main() {
    println(length("hello"))
}

مثال مضاد للاستدعاء الذاتي غير النهائي

fun badFactorial(n: Int): Long {
    if (n <= 1) return 1
    return n * badFactorial(n - 1)
}

fun main() {
    println(badFactorial(5))
}

تجنب تجاوز المكدس

tailrec fun count(n: Int, acc: Int = 0): Int {
    if (n == 0) return acc
    return count(n - 1, acc + 1)
}

fun main() {
    println(count(100000))
}

تحقق المترجم

tailrec fun gcd(a: Int, b: Int): Int {
    if (b == 0) return a
    return gcd(b, a % b)
}

fun main() {
    println(gcd(48, 18))
}

الاستدعاء الذاتي النهائي مقابل الحلقة

tailrec fun powerOfTwo(n: Int, acc: Long = 1): Long {
    if (n == 0) return acc
    return powerOfTwo(n - 1, acc * 2)
}

fun main() {
    println(powerOfTwo(10))
}

معاملات متعددة

tailrec fun fib(n: Int, a: Long = 0, b: Long = 1): Long {
    if (n == 0) return a
    return fib(n - 1, b, a + b)
}

fun main() {
    println(fib(20))
}

العكس باستخدام tailrec

tailrec fun reverse(s: String, acc: String = ""): String {
    if (s.isEmpty()) return acc
    return reverse(s.drop(1), s.first() + acc)
}

fun main() {
    println(reverse("kotlin"))
}

بحث عملي

tailrec fun indexOf(list: List<Int>, target: Int, i: Int = 0): Int {
    if (i >= list.size) return -1
    if (list[i] == target) return i
    return indexOf(list, target, i + 1)
}

fun main() {
    println(indexOf(listOf(5, 6, 7), 7))
}

تحقق سريع

مراجعة

tailrec fun sum(n: Int, acc: Int = 0): Int =
    if (n == 0) acc else sum(n - 1, acc + n)

fun main() {
    println(sum(50))
}