When using Java/Kotlin for programming is recommended to use Tail recursion or the Iterative version? Is there any difference in performance?

Question

I try to learn about good practices in programming and I'm stuck with this question. I know that in Java, recursive functions can be 'a pain in the ass' (sometimes), and I try to implement as much as I can the tail version of that function. Is it worth bothering with this or should I do in the old fashioned way? Is there any difference between this two functions (in Kotlin):

tailrec fun tail_fibonacci(n : BigInteger, fib1 : BigInteger = BigInteger.ZERO , fib2 : BigInteger = BigInteger.ONE) :
BigInteger {
    return when(n){
        BigInteger.ZERO -> fib1
        else -> tail_fibonacci(n.minus(BigInteger.ONE),fib1.plus(fib2),fib1)
    }
}

fun iterative_fibonacci(n: BigInteger) : BigInteger {
    var count : BigInteger = BigInteger.ONE
    var a : BigInteger = BigInteger.ZERO
    var b : BigInteger = BigInteger.ONE
    var c : BigInteger
    while(count < n){
        count += BigInteger.ONE
        c = a + b
        a = b
        b = c
    }
    return b
}

hotkey · Accepted Answer · 2017-09-05T18:22:58.340

The biggest difference I see is the signatures: while iterative_fibonacci takes one argument and is quite clear, tail_fibonacci takes three, and though the defaults are provided, this might surprise the user. You can, however, make a wrapper function for it, and even make the tailrec function a local one.

There should not be much difference in the resulting bytecode the two functions are compiled to, except for n.minus(BigInteger.ONE) vs count += BigInteger.ONE, and you can check it for yourself with a Kotlin bytecode viewer.

Regarding performance, there should not be any predictable difference between the two implementations (also note that the JVM additionally optimizes the code at runtime with JIT compiler), but of course the tailrec function is much more efficient than an ordinary recursive one would be.

As to the code style (which is highly opinion-based), many tail-recursive solutions look more natural (and closer to math notation), and some do not (e.g. when there are many parameters that end up in a complete mess).

So, I think, tailrec should be used as a performance tool (and especially as a way to avoid stack overflow, which requires all recursive calls to be tail ones) when you find a recursive definition more suitable for expressing what the code does.

score 2 · Answer 2 · answered Sep 05 '17 at 17:04

They are equivalent in terms of performance. Kotlin will optimize the recursion on tailrec functions, meaning it is identical to a loop based approach.

Whether you should prefer a functional or iterative approach really comes down to your own preference (and your team's, if applicable), taking into account readability, conciseness, and intuitiveness. This judgement may change from method to method; one function might be more readable using a functional approach, where another might benefit from a straightforward loop.

The nice thing about Kotlin is that it supports both approaches, and allows a developer to use the tool they need for the job.

When using Java/Kotlin for programming is recommended to use Tail recursion or the Iterative version? Is there any difference in performance?

2 Answers2