Kotlin – Tail recursive optimization

Tail recursion

Tail recursion is a special form of recursion in which a function has no other operation after calling itself. For example, what are the recursive algorithms for computing the NTH term of the Fibonacci sequence?

Simple recursive implementation

The 0 and 1 bits of the Fibonacci sequence are 1, and starting at the second, each term is the sum of the first two bits, so it is easy to implement using a recursive algorithm:

fun fib1(n: Int): Int {
    if (n == 0 || n == 1) return 1
    return fib1(n - 1) + fib1(n - 2);
}
Copy the code

This way, although the recursive call is on the last line of the method, there is also the operation of adding the results, which does not meet the definition of tail recursion.

Simple recursion is easy to understand, but in fact, the algorithm will have redundant computations, such as: fib1(2) will be executed many times, and the larger n is, the more redundant computations will be performed:

Tail recursion implementation

To solve the drawbacks of simple recursive implementation, we can save the calculated results and pass them to the next calculation, so we can optimize the recursive writing method:

fun fib2(n: Int): Int {
    return fibIter(1.1, n);
}

fun fibIter(a: Int, b: Int, n: Int): Int {
    Return if (n == 0) a else fibIter(b, a + b, n-1
    if (n == 0) {
        return a
    } else {
        return fibIter(b, a + b, n - 1)}}Copy the code

FibIter ()’s recursive code is in the last line of the method, and there is no other operation after the call, which conforms to the definition of tail recursion.

The performance comparison

In theory, we still need to use the actual code to test the running time of the two recursive algorithms, which can be more intuitive to see the difference. In order to facilitate the test, here is a time test method:

fun timeConsume(operation: () -> Unit) {
    val begin = System.currentTimeMillis()
    operation()
    val end = System.currentTimeMillis()
    println("begin = ${begin}ms , end = ${end}Ms, time-consuming${end - begin}ms")}Copy the code

Throw the two recursive algorithms into timeConsume(), and get the test result:

fun main(args: Array<String>) {
    timeConsume {
        println(fib1(45))}/ / 1836311903
    // begin = 1612368480299ms, end = 1612368486217ms, 5918ms

    timeConsume {
        println(fib2(45))}/ / 1836311903
    // begin = 1612368486217ms, end = 1612368486217ms, which takes 0ms
}
Copy the code

To get the value of Fibonacci’s 45th element, fib1() takes nearly 6s and fiB2 () 0ms. What a difference.

Note: Testing fiB1 (50) runs out of memory.

Tail recursive optimization (TAILREC)

Although the time consuming of the tail recursive algorithm mentioned above is very small, we know that the efficiency of recursive algorithm is not high, because each recursion needs to open up a method stack, which has performance consumption and may lead to memory overflow due to excessive recursion times, while the iterative algorithm does not have such problems:

fun fib3(n: Int): Int {
    if (n == 0 || n == 1) return 1
    var a = 1
    var b = 1
    for (i in 0 until n) {
        val a_ = b
        val b_ = a + b
        a = a_
        b = b_
    }
    return a
}
Copy the code

Similarly, let’s test the elapsed time of tail recursive algorithm and iterative algorithm:

fun main(args: Array<String>) {
    timeConsume {
        println(fib2(12000))}/ / 690383169
    // begin = 1612369032575ms, end = 1612369032578ms, which takes 3ms

    timeConsume {
        println(fib3(12000))}/ / 690383169
    // begin = 1612369032578ms, end = 1612369032579ms, which takes 1ms
}
Copy the code

Combining theory with practice, it can be seen from the test results that there is still a gap between tail recursive algorithm and iterative algorithm. If the COMPUTER CPU performance is low, or there is memory operation in the method, the gap will be larger.

Note: Because “to calculate the Fibonacci sequence n items” title only numerical run the algorithm, is too easy for the two algorithms, are millisecond level, therefore, need to pick up after the element calculation will be a little more than to see the gap, because too much recursion can appear out of memory at the same time, the value of n is also cannot too big, Test 15000 will run out of memory, 12000 will not.

Since recursion has this disadvantage, why don’t we stop using recursive algorithms in the future? Of course not. Recursion also has one great advantage, that is, the code logic is easy to understand. In this case, is there a way to make recursive algorithms perform as well as iterative algorithms? Indeed, Kotlin provides the tailrec keyword, which allows tail-recursive algorithms to automatically optimize their code at compile time, thus addressing the shortcomings of tail-recursive algorithms. We add fibIter() to tailrec:

fun fib2(n: Int): Int {
    return fibIter(1.1, n);
}

// only tailrec keyword is added
tailrec fun fibIter(a: Int, b: Int, n: Int): Int {
    return if (n == 0) a else fibIter(b, a + b, n - 1)}Copy the code

Then test the time consumption of fiB2 () and FIB3 () algorithms:

fun main(args: Array<String>) {
    timeConsume {
        println(fib2(50000))}/ / - 1256600222
    // begin = 1612370134450ms, end = 1612370134451ms, which takes 1ms

    timeConsume {
        println(fib3(50000))}/ / - 1256600222
    // begin = 1612370134452ms, end = 1612370134453ms, which takes 1ms
}
Copy the code

This is where the tailrec keyword, fib2(), which used to run out of memory once it passed 15000, now passes 50000 and takes the same time as the iterative algorithm fib3().

Note: tailrec keyword can only optimize tail recursive algorithms, other recursive algorithms cannot be optimized.