Kotlinで動的プログラミングを使用して純粋な関数を達成するにはどうすればよいですか？

Question

私のコードのいくつかを純粋な関数に変換しようとしてきましたが、私のcalculateFibonacci関数を純粋な関数にする方法を考えることができないこの単純なコードで、Kotlinを機能的に使う方法を学びました。

私は潜在的に再帰的な解決策を知っていますが、潜在的なスタックオーバーフローについてはどうでしょうか？KotlinはTail Call Optimizationを実装していますか？私はこの主旨をアップロード全体スニペットについては

 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

すべてのことは、命令的なアプローチから脱却し、シーケンス操作に関して考えることです。あなたがペアのシーケンスとしてそれを考えるならば、それははるかに容易になる

それはintのシーケンスとしてそれを考えることは非常に魅力的だからフィボナッチ数列の場合、それは難しいかもしれないが（からあなたは

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

：最終的にintのシーケンス）

だから、あなたは次のペアは、前の対の第二の要素と、前の組の要素の和として定義されているペアの無限列を作成することができますを導き出します

---

そして、あなたのメソッドをtailrecキーワードでマークすることで、テールコールの最適化を利用することができます。スタックオーバーフローの心配はありません。あなただけのfunキーワードの前にそれを適用します。

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 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 2

はKotlinは末尾呼び出しの最適化

を実装していないはい、tailrecキーワードがありますそれのために。

Answer 3

自家製についての詳細情報です。

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]