如何在 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)
}

以下是有关 Kotlin 中的尾递归的更多信息。

Answer 2

本土：

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]

Answer 3

> Kotlin 是否实现了尾部调用优化

是的，有tailrec关键字。