在编程中，我们通常会想到高级算法、人工智能或虚拟现实等超能力。但有时，一个超能力就隐藏在我们眼前，等待我们去发掘。Kotlin的尾递归（tailrec）就是这样一个看似简单的关键字，却蕴含着巨大的潜力。问题是，我们很多人并没有充分利用它。让我们一起探索它的奇妙之处，也许到最后你会质疑自己：“为什么我没有经常使用它呢？”

递归的一瞥

让我们以一个任务为例——计算列表中所有元素的和。使用递归来实现这个任务非常简洁。

fun sumList(nums: List<Int>): Int {
    if (nums.isEmpty()) return 0
    return nums.first() + sumList(nums.drop(1))
}

尽管这段代码简洁，但对于深度嵌套的列表来说，它可能会消耗掉我们的堆栈。

以 sumList(listOf(1, 2, 3)) 为例进行分解：

1 + sumList(listOf(2, 3)) 等待 sumList(listOf(2, 3)) 的结果，然后再加上 1。

2 + sumList(listOf(3)) 等待 sumList(listOf(3)) 的结果，然后再加上 2。

3 + sumList(emptyList()) 这里不需要等待。直接返回 3。

结果开始逐级返回： 3 + 2 返回 5。 5 + 1 返回 6。

如果有一种方法既保持简洁又摆脱其中的风险，那该多好啊？这就是尾递归的作用。

尾递归的介绍

尾递归重新定义了递归，使得函数的最后一个动作是调用自身，从而避免了额外的内存开销。

使用尾递归来计算列表的和：

tailrec fun sumList(nums: List<Int>, accumulator: Int = 0): Int {
    return if (nums.isEmpty()) {
        accumulator
    } else {
        sumList(nums.drop(1), accumulator + nums.first())
    }
}

注意到了吗？这里有一个累加器（accumulator），它保存着我们的结果，允许函数调用自身而不需要存储额外的数据。不再担心堆栈溢出错误了！

以 sumList(listOf(1, 2, 3)) 为例进行分解：

将 1 传递给累加器，然后使用 listOf(2, 3) 进行调用。

将 2 传递给累加器，然后使用 listOf(3) 进行调用。

将 3 传递给累加器，然后使用一个空列表进行调用。

返回累加器的值，即 6。

主要区别

调用栈

在非尾递归版本中，每一次递归调用都依赖于下一次的结果。这意味着每次调用都会被添加到调用栈中，并在完成之前一直保持在那里。对于一个很大的列表来说，这将耗尽调用栈，导致堆栈溢出错误。

执行方式

在尾递归版本中，每次调用都将其结果传递给下一次调用，并不需要等待后续调用的完成。这是一种“我做我的部分，然后将剩下的部分传递下去”的方式。

优化

由于非尾递归版本中存在依赖关系，编译器无法将其优化为循环。然而，尾递归版本在底层被转换为循环，这意味着即使对于包含数百万个元素的列表，也不会导致堆栈溢出。

在实际应用中，虽然简单的求和可能不会使用递归（而是使用其他方法），但是这里展示的原理同样适用于更复杂的算法和数据处理任务。理解标准递归和尾递归之间的基本区别有助于在Kotlin中编写更高效和更安全的递归函数。

其他示例

目录文件计数

假设你是一名软件工程师，正在开发一个云存储应用，类似于Google Drive或Dropbox。你被要求确定特定目录中文件的总数，包括所有子目录。

传统方法存在一个问题，如果用户有深度嵌套的目录，就有堆栈溢出的风险。

使用尾递归来解决这个问题：

tailrec fun countFilesTailRec(directories: List<Directory>, accumulator: Int = 0): Int {
    if (directories.isEmpty()) return accumulator
    val currentDir = directories.first()
    val remainingDirs = directories.drop(1)
    val filesInCurrentDir = currentDir.children.filterIsInstance<File>().size
    val subDirs = currentDir.children.filterIsInstance<SubDirectory>().map { it.directory }
    return countFilesTailRec(remainingDirs + subDirs, accumulator + filesInCurrentDir)
}

数学表达式求值

常见的用例是对嵌套的数学运算进行求值。这里我们将实现一个简化版的求值器，用于对嵌套的加法进行求值。

sealed class Expression
data class Value(val number: Int) : Expression()
data class Addition(val left: Expression, val right: Expression) : Expression()

tailrec fun evaluate(expression: Expression, accumulator: Int = 0): Int = when (expression) {
    is Value -> accumulator + expression.number
    is Addition -> evaluate(expression.right, accumulator + when (val leftExpr = expression.left) {
        is Value -> leftExpr.number
        else -> evaluate(leftExpr)
    })
}

fun main() {
    val expression = Addition(
        Addition(Addition(Value(1), Value(2)), Addition(Value(3), Value(4))),
        Addition(Value(15), Value(-2))
    )
    println(evaluate(expression))  // Output: 23
}

路径查找算法

对于游戏或地图应用程序，人们可能需要确定两点之间的最短路径。尾递归可以通过跟踪访问的节点来帮助深度优先搜索 (DFS) 或广度优先搜索 (BFS) 等算法，而无需担心大型映射中堆栈溢出的风险。

计算员工层次结构

在员工向经理报告的组织中，如果您想计算经理（直接和间接）领导下的报告者数量，尾递归可以帮助在层次结构中导航，而不会耗尽堆栈。

网页抓取任务

当递归地解析网页以提取信息时（例如跟踪一定深度的链接），尾递归可以确保在存在大量嵌套链接时不会遇到堆栈溢出问题。

系统依赖性检查

当安装具有多个依赖项的新软件包时，系统可能会递归地检查每个依赖项是否存在。使用尾递归可以防止潜在的堆栈溢出问题。

Tail Recursion — Yes or Not?

如果您必须搜索列表中的项目，尾递归会有用吗？

记住

简单性——尾递归方法是否简化了您的代码？
深度——你是否经常期待深度递归？如果没有，传统的递归或循环可能就足够了。
效率——它是否具有性能优势？做一些基准测试！

二分查找

假设您正在编写一个二分搜索函数。应该使用尾递归吗？请记住这些指示 —

递归深度：对大小为 1,024 的列表进行二分查找最多只会递归 10 次。无需尾递归
清晰度：尾递归版本读起来是否清晰？如果没有，迭代解决方案可能是最好的。
性能：确保尾递归版本提供显着性能改进的基准。

总结

简而言之，虽然尾递归很有效，但始终要权衡其好处与其他方法的可读性和简单性。如果 for 循环或简单的映射操作可以清楚地完成工作，则不要强制尾递归。

Kotlin 的 tailrec 仅仅是一个工具；它使用简单，代码稍作调整，就可以了。所以下次遇到递归任务时，请记住 tailrec 。

玖叶教程网

前端编程开发入门

Kotlin的尾递归(tailrec)是如何提供更智能的循环方式的?

递归的一瞥

尾递归的介绍

主要区别

其他示例

Tail Recursion — Yes or Not?

总结