Kotlin Academy · 课时

tailrec 函数

Q: 「tailrec 函数」这节课中我会学到什么？

优化递归 你通过在浏览器中直接运行的动手代码来练习 Kotlin Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

优化递归

第 3 / 4 课13 个步骤

tailrec 函数 是 CoddyKit 上的免费 Kotlin Academy 课时。这是第 3 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 Kotlin Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Kotlin Academy 课程共包含 4 节课。

什么是尾递归

当递归调用是函数执行的最后一个操作时，该函数就是尾递归函数。这样 Kotlin 就可以将其优化为循环，避免栈溢出。

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

fun main() {
    countdown(3)
}

tailrec 修饰符

添加 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"))
}

非尾递归反例

这个阶乘函数不是尾递归，因为乘法发生在调用返回之后。如果将其标记为 tailrec，编译器会发出警告。

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

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

避免栈溢出

没有 tailrec 的深度递归可能导致程序崩溃。使用它后，即使输入很大，也能使用固定的栈空间运行。

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，但调用不处于尾部位置，编译器会发出警告且不会进行优化。请重视该警告。

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 函数编译后生成的代码大致与等价循环相同，但它以递归方式表达算法。

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 会将处于尾部位置的递归转换为循环，从而避免栈溢出。
递归调用必须是最后一个操作。
使用累加器参数来实现尾递归形式。
当函数无法优化时，编译器会发出警告。

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

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

免费开始

用 AI 导师学习 Kotlin — 免费

在浏览器中编写并运行真实代码，获得全天候 AI 导师的即时帮助，并在网页或应用中继续学习。

课程: 51
课程: 203

免费开始学习查看完整课程

常见问题解答

「tailrec 函数」课时是免费的吗？

是的 — 「tailrec 函数」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Kotlin Academy 课程的其余内容，请升级到 CoddyKit PRO。 Kotlin Academy 课程共包含 4 节课。

「tailrec 函数」这节课中我会学到什么？

优化递归你通过在浏览器中直接运行的动手代码来练习 Kotlin Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Kotlin Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Kotlin Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 3 节课，共 4 节。

「tailrec 函数」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Kotlin Academy 课中编写并运行代码吗？

能。每节 Kotlin Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 Kotlin Academy