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

发布时间：2020-12-15 03:01:18 所属栏目：Java 来源：网络整理

导读：我试着学习编程中的好习惯,我坚持这个问题.我知道在 Java中,递归函数可能是“痛苦的屁股”(有时),我尝试尽可能多地实现该函数的尾部版本.是否值得为此烦恼,还是应该以老式的方式做？这两个函数之间有什么区别(在Kotlin中)： tailrec fun tail_fibonacci(n :

我试着学习编程中的好习惯,我坚持这个问题.我知道在 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函数成为 local one.

除了n.minus(BigInteger.ONE)vs count = BigInteger.ONE之外,编译两个函数的结果字节码应该没有太大区别,你可以用a Kotlin bytecode viewer自己检查它.

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

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

因此,我认为,当你发现一个更适合表达代码的递归定义时,tailrec应该被用作一个性能工具(特别是作为一种避免堆栈溢出的方法,它要求所有递归调用都是尾部调用).

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!