kotlin - 如何让Kotlin意识到此BST比较功能是尾递归的？

Question

这是我放在一起的一个简单的Binary Search Tree类。

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

如Tail recursive functions中所述:

To be eligible for the tailrec modifier, a function must call itself as the last operation it performs. You cannot use tail recursion when there is more code after the recursive call, and you cannot use it within try/catch/finally blocks.

在那里，您的实现已因第一个约束再次调用函数本身而失败。即使调用此函数，它也位于另一个实例，而不是此块的最后一个操作。

我能想到的最好的办法是在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)
        }
    }
}

但是，另外，您应该考虑实现空值模式，而不是对left和right使用可空值。您可以为此使用 Sealed Classes。