Menu
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
}
574
Rules for Tail Recursion in Kotlin To implement a function in Kotlin using tail recursion, there is one rule to follow: the recursive call must be the very last call of the method. This works perfectly well.
Kotlin compiler just converts the Tail Call Optimized function to iterative way. Hence no new stack frame is created. With tailRec keyword, you can write the function in Tail Call optimized way, but internally it converts it to iterative function and runs the iterative().
The tail recursion is better than non-tail recursion. As there is no task left after the recursive call, it will be easier for the compiler to optimize the code. When one function is called, its address is stored inside the stack. So if it is tail recursion, then storing addresses into stack is not needed.
Java supports tail-recursive calls, but AFAIK it doesn't optimize them away.
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.
96
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.
2
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
