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

Question

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

Answer 1

我看到的最大区别是签名： whileiterative_fibonacci需要一个参数并且非常清晰，而tail_fibonacci需要三个参数，尽管提供了默认值，但这可能会让用户感到惊讶。但是，您可以为其创建一个包装函数，甚至使该函数成为本地tailrec函数。

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

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

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

因此，我认为，tailrec当您发现更适合表达代码功能的递归定义时，应该将其用作性能工具（尤其是作为避免堆栈溢出的方法，这要求所有递归调用都是尾调用）。