java - 在使用 Java/Kotlin 进行编程时，推荐使用 Tail recursion 还是 Iterative 版本？性能上有区别吗？

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

我看到的最大区别是签名:虽然 iterative_fibonacci 采用一个参数并且非常清晰，但 tail_fibonacci 采用三个参数，虽然提供了默认值，但这可能会令人惊讶用户。但是，您可以为其创建一个包装函数，甚至将 tailrec 函数设置为 local one .

除了 n.minus(BigInteger.ONE) 与 count += BigInteger.ONE 之外，这两个函数编译成的结果字节码应该没有太大区别>，您可以通过a Kotlin bytecode viewer 自行查看.

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

就代码风格(高度基于意见)而言，许多尾递归解决方案看起来更自然(更接近数学符号)，有些则不然(例如，当有许多参数以完整的形式结束时)困惑)。

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