这个尾部是递归的还是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语句中，你进行递归调用，此时抛出的当前调用被抛出，因为递归调用的结果就是你需要的所有内容。

---

我不确定你的算法本身是否正确，因为第一个未访问过的孩子将是唯一一个进行递归调用的孩子。