这是尾递归问题还是 Kotlin 编译器的问题？

Question

如果以下函数是尾递归的，或者 Kotlin 编译器或 IntelliJ Idea 有问题，我有点困惑。

据我了解，这不符合 tailrec 优化条件，因为递归调用不是最后一次调用。这是代码；

    tailrec fun hasRouteBetween(first: GraphNode, second: GraphNode): Boolean {
        if (first.id == second.id) return true

        if (second.children.isEmpty()) return false

        second.visited = true

        for (child in second.children) {
            if (!child.visited) {
                return hasRouteBetween(first, child)
            }
        }
        return false
    }

data class GraphNode(val id: Int, var visited: Boolean = false, val children: LinkedList<GraphNode>)

根据 Kotlin 文档、论坛帖子和我发现的一些 SO 答案，这种用法应标记为警告。

我也在 IntelliJ Kotlin 编译器上启用了编译器警告。但是我在 IntelliJ（IntelliJ IDEA 2018.3.3（终极版 - Build #IU-183.5153.38，构建于 2019 年 1 月 9 日）或 Gradle (5.2) 上没有看到任何警告。我使用 Kotlin 1.3 Java 1.8_141.

我在这里错过了什么？（我想确保我正确使用 tailrec，因为此代码将与其他人共享）。任何帮助，将不胜感激。

Answer 1

这个函数是尾递归的。尾递归工作需要的是递归调用直接产生函数的结果，而不需要在进行调用的地方进行任何额外处理。这确保了在递归调用开始之前可以清除当前函数调用的堆栈，因为那里的数据不再需要了。

例如，这个实现是行不通的，因为它需要在递归的每一层都保持堆栈的状态：

var result = false
for (child in second.children) {
    if (!child.visited) {
        if (hasRouteBetween(first, child)) {
            result = true
        }
    }
}
return result

您的函数不需要执行此类操作。在你的 if 语句中，你进行了递归调用，此时无论当前调用发生了什么都被抛出，因为递归调用的结果就是你所需要的。

我不确定您的算法本身是否正确，因为第一个未访问的 child 将是唯一被递归调用的算法。

这是尾递归问题还是 Kotlin 编译器的问题？

Is this tail recursive or issue with the Kotlin compiler?

tail-recursion

intellij-idea

kotlin