functional-programming - Kotlin中如何用动态编程实现纯函数？

Question

我一直在尝试将一些代码转换为纯函数，以学习如何以函数方式使用 Kotlin，通过这个简单的代码片段，我想不出任何方法来让我的 calculateFibonacci 函数是一个纯函数。

我知道一个潜在的递归解决方案，但是潜在的堆栈溢出又如何呢？Kotlin 是否实现了尾部调用优化？

示例:

     val fibonacciValues = hashMapOf<Int, BigInteger>(0 to BigInteger.ONE, 1 to BigInteger.ONE);

 // * TODO investigate how to do dynamic programming with a pure function ** //
    private fun calculateFibonacci(n: Int): BigInteger? {
        if (fibonacciValues.contains(n)) {
            return fibonacciValues.get(n)
        } else {
            val f = calculateFibonacci(n - 2)!!.add(calculateFibonacci(n - 1))

            fibonacciValues.put(n, f)
            return f
        }
    }

对于整个片段，我上传了这个要点: https://gist.github.com/moxi/e30f8e693bf044e8b6b80f8c05d4ac12

Answer 1

整个事情是关于突破命令式方法并根据序列操作进行思考。

就斐波那契数列而言，这可能会很棘手，因为很容易将其视为整数序列，但如果将其视为成对序列，事情就会变得容易得多 (最终从中派生出一个整数序列)

因此，您可以创建一个无限的对序列，其中下一个对被定义为前一个对的第二个元素以及前一个对中的元素之和:

generateSequence(1 to 1) { it.second to it.first + it.second }
  .map { it.first }

<小时/>

是的，您可以通过使用 tailrec 关键字标记您的方法来利用尾部调用优化 - 不用担心堆栈溢出。您只需在 fun 关键字之前应用它即可:

fun fibonacciAt(n: Int) = {
    tailrec fun fibonacciAcc(n: Int, a: Long, b: Long): Long {
        return when (n == 0) {
            true -> b
            false -> fibonacciAcc(n - 1, a + b, a)
        }
    }

    fibonacciAcc(n, 1, 0)
}

以下是有关 Tail Recursion in Kotlin. 的更多信息