Kotlin recursion stack overflow

Question

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?

Or should I write it in such a way that the recursive call is made on the tailing line of the function to allow the compiler to optimize with tail recursion? I don't fully understand how the compiler optimizes for tail recursion. — Thomas Cook, Jun 23 '18 at 20:45
I've edited the question to use tail recursion as the same problem still occurs! — Thomas Cook, Jun 23 '18 at 20:47
Koltin compiler does not optimize for tail recursion (yet). You can use extension functions on collections instead of recursion. — m0skit0, Jun 23 '18 at 20:49

Alexander Egger · Accepted Answer · 2018-06-24T09:59:17.207

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!

@ThomasCook see https://stackoverflow.com/questions/33923/what-is-tail-recursion for a detailed description of how tail recursion works — Alexander Egger, Jun 24 '18 at 09:17
Added a version of the function without recursion to show how the compiler converts the recursion into a loop — Alexander Egger, Jun 24 '18 at 10:00

Kotlin recursion stack overflow

1 Answers1