Как я могу сделать 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?.contains в оператор if, который проверяет значение left == null , возникает другая ошибка о том, как left изменен и может быть изменен с помощью оператора if . Как я могу сделать эти образы хвостом рекурсивными в глазах котлина?

Как указано в рекурсивных функциях хвоста :

Чтобы иметь право на модификатор tailrec , функция должна вызывать себя как последнюю выполняемую им операцию. Вы не можете использовать рекурсию хвоста, когда после рекурсивного вызова появляется больше кода, и вы не можете использовать его в блоках try / catch / finally.

Там ваша реализация завершается уже с первым ограничением, чтобы снова вызвать функцию. Даже если вы вызываете эту функцию, она находится в другом экземпляре, а также не последней операции этого блока.

Лучшее, что я мог придумать, было внедрить его «статически» в контексте Котлина .

 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) } } } 

Но дополнительно вы должны рассмотреть возможность реализации шаблона с нулевым значением вместо использования значений с нулевым значением для левого и правого. Для этого вы можете использовать Sealed Classes .