Этот хвост рекурсивный или проблема с компилятором Kotlin? - PullRequest
Новая
       7

Этот хвост рекурсивный или проблема с компилятором Kotlin?

0 голосов
/ 17 февраля 2019

Я немного смущен, если следующая функция является хвостовой рекурсивной, или у компилятора 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 (Ultimate Edition - сборка № IU-183.5153.38, построена 9 января 2019 г.) или Gradle (5.2). Я использую Kotlin 1.3 с Java 1.8_141.

Что мне здесь не хватает? (Я хочу убедиться, что я правильно использую tailrec, потому что этот код будет предоставлен другим). Любая помощь будет принята.

1 Ответ

0 голосов
/ 17 февраля 2019

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

Так, например, эта реализация не будет работать, потому что она нуждается вчтобы сохранить состояние стека на каждом уровне рекурсии: 

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

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

I 'Я не уверен, что ваш алгоритм корректен таким образом, так как первый ревизион будет единственным, к которому будет сделан рекурсивный вызов.

...