我怎样才能让kotlin认识到这个BST比较函数是尾递归的？

这是一个简单的二进制搜索树类，我把它放在一起。

data class Bst<T: Comparable<T>>(var left: Bst<T>?, var value: T, var right: Bst<T>?) { tailrec fun contains(key: T): Boolean { return if (key < value) { left?.contains(key) ?: false } else if (key > value) { right?.contains(key) ?: false } else { true } } } 

不幸的是，当我把它粘贴到try.kotlinlang.org时 ，它说递归调用不是尾递归的。 如果我重构left?.contains代码，将代码包含到测试left == null的if语句中，则会出现另一个关于left是如何变化的错误，以及自if语句以来可能发生的变化。 我怎样才能使这些调用尾巴在kotlin的眼睛递归？

Answer 1

就像在尾递归函数中所述 ：

要符合tailrec修饰符的条件，函数必须调用它自己作为它执行的最后一个操作。 在递归调用之后有更多的代码时，您不能使用尾递归，并且不能在try / catch / finally块中使用它。

在那里你的实现已经失败，第一个约束再次调用函数本身。 即使你调用这个函数，也是在另外一个实例上，也不是这个块的最后一个操作。

我能想到的最好的方法是在Kotlin环境中“静态”实现它。

 data class Bst<T: Comparable<T>>(var left: Bst<T>?, var value: T, var right: Bst<T>?) { fun contains(key: T) = contains(key, this) companion object { tailrec fun <T: Comparable<T>> contains(key: T, bst: Bst<T>): Boolean { if (key == bst.value) return true val bst2 = bst.run { if (key < value) left else right } if (bst2 == null) return false return contains(key, bst2) } } } 

但另外你应该考虑实现一个空值模式，而不是使用左和右的空值。 你可以为此使用密封类 。