CODEWITHSUNDEEP
recursionkotlinstack-overflowtail-recursion
Thomas Cook
Thomas Cook

Reputation: 4853

Kotlin recursion stack overflow

I have written this recursive function in 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)
}

It will run an indeterminate amount of times (because I'm using randomness to converge on solution in evolutionary algorithm). I am frequently getting stack overflow. What is the maximum stack depth for Kotlin/JVM languages? Should i just write the function non recursively?

Upvotes: 3

Views: 1664

Answers (1)

Alexander Egger
Alexander Egger

Reputation: 5300

The tailrec keyword tells the Kotlin compiler to use tail recursion. It therefore unrolls the recursion into a loop and this way you get rid of the 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)
}

So when using tailrec the compiler creates something which matches to following function: 

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

In this function no method calls are made any more therefore nothing gets pushed to the stack and we are save from StackOverflowError.

Note that we can still run into an endless loop!

Upvotes: 9

Related Questions