如何在 Kotlin 中用动态规划实现一个纯函数？

Question

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

我知道一个潜在的递归解决方案，但潜在的堆栈溢出又如何呢？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

does Kotlin implements Tail Call Optimization

是的，有 tailrec 关键字。

Answer 2

整个事情就是要打破命令式的方法，从序列操作的角度来思考。

对于斐波那契数列，这可能会很棘手，因为很容易将其视为整数序列，但 如果您将其视为对序列，它会变得容易得多（你最终会从中导出一个整数序列）

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

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.

的更多信息

Answer 3

本土：

fun fib(i: Int): Int {
    tailrec fun go(k: Int, p: Int, c: Int): Int {
        return if (k == 0) p
        else go(k - 1, c, p + c)
    }

    return go(i, 0, 1)
}

generateSequence 实际上显示了斐波那契实现作为示例。

fun fibonacci(): Sequence<Int> {
    // fibonacci terms
    // 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, ...
    return generateSequence(Pair(0, 1), { Pair(it.second, it.first + it.second) }).map { it.first }
}

println(fibonacci().take(10).toList()) // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

如何在 Kotlin 中用动态规划实现一个纯函数？

How to achieve a pure function with dynamic programming in Kotlin?

functional-programming

tail-recursion

kotlin