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语言的最大堆栈深度是多少？我应该非递归地编写函数吗？

Answer 1

该tailrec关键字告诉科特林编译器使用尾递归.因此它将递归展开到循环中,这样就可以摆脱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中保存.

请注意,我们仍然可以遇到无限循环!