ฟังก์ชัน tailrec

การเรียกซ้ำแบบหางคืออะไร

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

fun main() {
    countdown(3)
}

ตัวแก้ไขการเรียกซ้ำแบบหาง

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))
}

รูปแบบ Accumulator

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))
}