CodeWars Going to zero or to infinity? Kotlin实现优化求助

这是CodeWars平台的一道编程kata题目：我最初使用Double类型实现逻辑，但计算30!及以上阶乘时必须改用BigDecimal类型；迭代到200!计算场景优化代码后遇到执行超时问题，超时阈值为16000ms。
现有需求是实现可快速计算200!以上阶乘的代码，解决大参数下的运行异常问题。

初始版本（仅支持200!以内计算） #

最初编写的代码可正常通过200!以内的全部简单测试，但随机测试用例n超过200时就会触发超时；代码在本地IDEA环境运行无问题，但CodeWars服务器端无法在时限内完成计算，初始代码如下：

fun going(n: Int): Double {
    val factorial = factorial(n)
    val zeroField = zero(factorial)
    val infiniteField = infinite(n)

    val beforeRound = zeroField.multiply(infiniteField)
    return beforeRound.setScale(6, RoundingMode.DOWN).toDouble()
}

fun factorial(n: Int): BigDecimal{
    if (n<=1) return BigDecimal.ONE

    return BigDecimal(n).multiply(factorial(n-1))
}

fun infinite(n: Int): BigDecimal {
    var sumFact = BigDecimal(0)
    var factCounter = 1
    repeat(n){
        sumFact += factorial(factCounter)
        factCounter++
    }
    return sumFact
}

fun zero(factorial: BigDecimal): BigDecimal{
    return BigDecimal.ONE.divide(factorial, MathContext.DECIMAL128)
}

HashMap缓存优化版本（支持n<1000场景） #

在其他用户提示下，我尝试使用HashMap缓存阶乘计算结果，该版本可支持n<1000的场景，但n大于约5800时会抛出主线程栈溢出异常java.lang.StackOverflowError。我的目标是支持10000!这类超大阶乘计算，加入HashMap缓存的代码如下：

val myFactorialHash = mutableMapOf<Int, BigDecimal>(1 to BigDecimal.ONE)


    fun going(n: Int): Double {
        
        println(n)

        val factorial = factorial(n)
        val zeroField = zero(factorial)
        val infiniteField = infinite(n)

        val beforeRound = zeroField.multiply(infiniteField)
        return beforeRound.setScale(6, RoundingMode.DOWN).toDouble()
    }

    fun factorial(n: Int): BigDecimal{
        if (n<=1){
            return myFactorialHash[1]!!
        }

        if (myFactorialHash.containsKey(n)){
            return myFactorialHash[n]!!
        } else {
            myFactorialHash[n] = BigDecimal(n).multiply(factorial(n-1))
        }

        return myFactorialHash[n]!!
    }

    fun infinite(n: Int): BigDecimal {
        var sumFact = BigDecimal(0)
        var factCounter = 1
        repeat(n){
            sumFact += factorial(factCounter)
            factCounter++
        }
        return sumFact
    }

    fun zero(factorial: BigDecimal): BigDecimal{
        return BigDecimal.ONE.divide(factorial, MathContext.DECIMAL128)
    }

尾递归修饰符测试 #

针对递归tailrec尾递归修饰符做了对照测试：实际实验中添加tailrec修饰与不添加没有明显差异，n=7027时运行正常，n=7028时触发栈溢出异常，实验代码如下：

fun main(){
    println(factorial(7027))
}

tailrec fun factorial(n: Int): BigDecimal{
    if (n<1) return BigDecimal.ONE
    return BigDecimal(n).multiply(factorial(n-1))
}

预初始化哈希缓存版本 #

调试5小时后，我尝试按最大栈容量预初始化哈希缓存，对应代码如下：

val myFactorialHash = mutableMapOf<Int, BigDecimal>(1 to BigDecimal.ONE)

    fun going(n: Int): Double {
        initHash()
        val factorial = factorial(n)
        val zeroField = zero(factorial)
        val infiniteField = infinite(n)

        val beforeRound = zeroField.multiply(infiniteField)
        return beforeRound.setScale(6, RoundingMode.DOWN).toDouble()
    }

    fun factorial(n: Int): BigDecimal{
        if (n<=1){
            return myFactorialHash[1]!!
        }

        var counter = n

        if (myFactorialHash.containsKey(n)){
            return myFactorialHash[n]!!
        } else {
            myFactorialHash[n] = BigDecimal(n).multiply(factorial(n-1))
        }

        return myFactorialHash[n]!!
    }

    fun infinite(n: Int): BigDecimal {
        var sumFact = BigDecimal(0)
        var factCounter = 1
        repeat(n){
            sumFact += factorial(factCounter)
            factCounter++
        }
        return sumFact
    }

    fun zero(factorial: BigDecimal): BigDecimal{
        return BigDecimal.ONE.divide(factorial, MathContext.DECIMAL128)
    }

    fun initHash(){
        repeat(7000){
            myFactorialHash[it] = factorial(it)
        }
    }

极简1行代码实现原理 #

我最终通过BigDecimal哈希缓存方案通过了题目，但看到题解区的极简实现时大受震撼，该方案仅用1行代码就实现了全部需求，代码如下：

fun going(n: Int): Double = if (n == 0) 0.0 else 1 + going(n - 1) / n

这个实现的核心是对题目要求的计算公式做了数学化简，完全避开了超大数计算：
题目实际要求计算的是(1! + 2! + 3! + ... + n!) / n!，我们记这个结果为f(n)，对式子做拆分：

• f(n) = [n! + (1! + 2! + ... + (n-1)!)] / n!
• 拆分后得到 f(n) = 1 + (1! + 2! + ... + (n-1)!)/n!
• 把分母n!拆成n*(n-1)!，就可以得到 f(n) = 1 + [(1! + 2! + ... + (n-1)!)/(n-1)!]/n = 1 + f(n-1)/n

按照这个递推式直接用Double类型计算即可，不需要引入BigDecimal处理超大阶乘，不会出现超时、栈溢出问题，n到十万级都可以瞬间完成计算，精度也完全满足题目保留6位小数的要求。

内容的提问来源于stack exchange，提问作者elenaovchinnikova