Переполнение стека рекурсии Kotlin - PullRequest
Новая
       47

Переполнение стека рекурсии Kotlin

0 голосов
/ 23 июня 2018

Я написал эту рекурсивную функцию в 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?Должен ли я просто написать функцию не рекурсивно?

1 Ответ

0 голосов
/ 24 июня 2018

Ключевое слово 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 .

Обратите внимание, что мы все еще можем столкнуться с бесконечным циклом!

...