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
}
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.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments