使用Java/Kotlin编程时推荐使用Tail recursion还是Iterative版本？性能有什么区别吗？

Question

我试图了解编程方面的良好做法，但我被这个问题困住了。我知道在 Java 中，递归函数可以是 'a pain in the ass'（有时），并且我尝试尽可能多地实现该函数的尾部版本。值得为此烦恼还是我应该以老式的方式做？这两个函数有什么区别（在 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
}

Answer 1

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

您是应该更喜欢函数式方法还是迭代式方法实际上取决于您自己的偏好（以及您的团队的偏好，如果适用），同时考虑可读性、简洁性和直观性。这种判断可能会因方法而异；使用函数式方法，一个函数可能更具可读性，而另一个函数可能会受益于简单的循环。

Kotlin 的优点在于它支持这两种方法，并允许开发人员使用他们完成工作所需的工具。

Answer 2

我看到的最大区别是签名：iterative_fibonacci 接受一个参数并且非常清楚，而 tail_fibonacci 接受三个参数，虽然提供了默认值，但这可能会让用户感到惊讶。但是，您可以为它创建一个包装函数，甚至可以将 tailrec 函数设为 local one.

除了 n.minus(BigInteger.ONE) 和 count += BigInteger.ONE 之外，这两个函数编译后的字节码应该没有太大区别，您可以使用自行检查。

关于性能，两种实现之间应该没有任何可预测的差异（还要注意，JVM 在运行时使用 JIT 编译器额外优化代码），但当然 tailrec 函数效率更高比普通的递归要好。

至于代码风格（高度基于意见），许多尾递归解决方案看起来更自然（并且更接近数学符号），而有些则不然（例如，当有很多参数以一团糟）。

所以，我认为，tailrec 应该用作一种性能工具（尤其是作为一种避免堆栈溢出的方法，这要求所有递归调用都是尾调用）当你找到一个递归定义时适合表达代码的作用。

使用Java/Kotlin编程时推荐使用Tail recursion还是Iterative版本？性能有什么区别吗？

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

java

kotlin

tail-recursion