如何在Kotlin中用动态编程实现一个纯函数?

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

我意识到一个潜在的递归解决方案,但是对于潜在的堆栈溢出呢,Kotlin是否实现了Tail Call Optimization?

例:

  val fibonacciValues = hashMapOf(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

整个事情就是要摆脱顺序操作的必要方法和思考。

在斐波那契数列的情况下,这可能是棘手的,因为它很容易被认为是一系列的Ints,但是如果把它想象成一系列对 (从中最终得到一系列Ints )

所以,你可以创建一个无限序列的对,其中下一对被定义为前一对的第二个元素和前一对元素的和:

 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尾部递归的更多信息。

自产自销:

 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 { // 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是否实施了尾巴呼叫优化?

是的,有关于tailrec关键字。