Kotlin 递归堆栈溢出问题

Question

我已经用 Kotlin 编写了这个递归函数：

fun recursive(target: String, population: Population, debugFun: (String) -> Unit) : Population {
    if (population.solution(target).toString() == target) {
        return population
    }
    debugFun.invoke(population.solution(target).toString())
    return recursive(target, population.evolve(target), debugFun)
}

这段代码会运行不确定的次数（因为我正在使用随机性来收敛进化算法的解决方案）。但我经常会遇到堆栈溢出的情况。 Kotlin / JVM语言的最大堆栈深度是多少？我应该写一个非递归的函数吗？

- Thomas Cook

---

或者我应该这样编写函数，使得递归调用在函数的尾行进行，以便允许编译器优化尾递归？我并不完全理解编译器如何针对尾递归进行优化。 - Thomas Cook

我已经编辑了问题，使用尾递归，因为相同的问题仍然存在！ - Thomas Cook

Kotlin编译器目前尚未针对尾递归进行优化。您可以使用集合的扩展函数来替代递归。 - m0skit0

Answer 1

< p > tailrec 关键字告诉 Kotlin 编译器使用尾递归。它将递归展开为循环，这样就可以摆脱StackOverflowError。

tailrec fun recursive(target: String, population: Population, debugFun: (String) -> Unit) : Population {
    if (population.solution(target).toString() == target) {
        return population
    }
    debugFun.invoke(population.solution(target).toString())
    return recursive(target, population.evolve(target), debugFun)
}

因此，在使用tailrec时，编译器会创建一个与以下函数匹配的内容：

fun recursive(target: String, population: Population, debugFun: (String) -> Unit) : Population{
    var tmp = population

    while (true) {
        if (tmp.solution(target).toString() == target) {
            return tmp
        }
        debugFun.invoke(population.solution(target).toString())
        tmp = tmp.evolve(target)
    }
}

在这个函数中不再进行任何方法调用，因此没有任何东西会被推到堆栈中，我们就可以避免StackOverflowError了。

请注意，我们仍然可能会进入无限循环！

- Alexander Egger

---

@ThomasCook 请查看 https://dev59.com/5HVD5IYBdhLWcg3wRpaX 了解尾递归的详细描述。 - Alexander Egger

添加了一个不使用递归的函数版本，以展示编译器如何将递归转换为循环。 - Alexander Egger