当使用Java / Kotlin进行编程时,建议使用尾递归还是迭代版本? 性能有什么不同?

我试图了解编程中的良好实践,我坚持这个问题。 我知道,在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 } 

我看到的最大的区别是签名:虽然iterative_fibonacci接受一个参数,很清楚, tail_fibonacci需要三个,尽管提供了默认值,这可能会让用户感到惊讶。 但是,您可以为它创建包装函数,甚至可以使tailrec函数成为本地函数。

除了n.minus(BigInteger.ONE)count += BigInteger.ONE之外,这两个函数编译的结果字节码应该没有太大差别,您可以使用Kotlin字节码查看器 n.minus(BigInteger.ONE)检查。

关于性能,这两个实现之间不应该有任何可预测的差异(另请注意,JVM在运行时使用JIT编译器进一步优化了代码),但是当然tailrec函数比普通的递归函数更有效率。

至于代码风格(这是高度基于意见的),许多尾递归的解决方案看起来更自然(更接近数学符号),有些则不(例如,当有许多参数完全混乱时)。

所以,我认为, tailrec应该被用作性能工具(特别是作为一种避免堆栈溢出的方式,当所有递归调用都是尾部调用时),当你find一个更适合expression代码的递归定义的时候。

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

考虑到可读性,简洁性和直观性,是否应该选择function性还是迭代性方法,确实取决于您自己的偏好(以及您的团队,如果适用)。 这个判断可能会随着方法的不同而改变。 一个function可能更可读性使用function的方法,另一个可能受益于一个简单的循环。

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