当使用Java/Kotlin进行编程时，建议使用尾递归或迭代版本？性能有什么不同？

我尝试了解编程中的良好实践，并坚持这个问题。我知道在Java中，递归函数可能是'屁股疼痛'（有时），我尽可能实现该函数的尾部版本。这是值得一提的，或者我应该以旧式的方式做？有（在科特林）这两种功能之间的任何差别：当使用Java/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 
}

来源

2017-09-05 Andrei Paciurca

我看到的最大的区别是签名：当iterative_fibonacci需要一个参数，是相当清楚的，tail_fibonacci有三个，虽然设置了默认值，这可能会惊讶的用户。但是，您可以为它制作包装函数，甚至可以使tailrec函数为local one。

除了n.minus(BigInteger.ONE)与count += BigInteger.ONE之外，这两个函数的结果字节码应该没有太大差别，您可以用a Kotlin bytecode viewer自行检查。

关于性能，两个实现之间不应该有任何可预测的差异（还要注意JVM在运行时使用JIT编译器额外优化了代码），但当然tailrec函数比普通递归函数将会。对于代码风格（这是高度基于观点的），许多尾递归解决方案看起来更自然（更接近数学符号），有些则不（例如，当有许多参数以完成一塌糊涂）。

因此，我认为，tailrec应该用作性能工具（特别是作为一种避免堆栈溢出的方法，它要求所有递归调用都是尾部调用），当您找到递归定义更适合于表达什么代码呢。

来源

2017-09-05 17:04:45 hotkey

它们在性能方面等同的。 Kotlin将优化tailrec函数的递归，这意味着它与基于循环的方法相同。

无论你应该更喜欢功能性的或迭代的方法真的可以归结为自己的喜好（和你的团队的，如果适用），同时考虑到可读性，简洁，和直观。这种判断可能会随着方法而变化;一个函数可能更易于使用函数式方法，另一个函数可能从一个简单的循环中受益。

Kotlin的好处在于它支持两种方法，并允许开发人员使用他们需要的工具。

来源

2017-09-05 17:04:32

当使用Java/Kotlin进行编程时，建议使用尾递归或迭代版本？性能有什么不同？

回答

相关问题