scala - 再帰を使用した高速フィボナッチ

Question

Scala でフィボナッチ関数を実装しましたが、正常に動作しますが、50 を入力すると、毎回前の 2 つの整数を計算する必要があるため、計算に時間がかかります。前の2つの数字を保持する関数を見つけました。ただし、この関数を作成して、3 ではなく 2 つの整数を受け入れ、特定のインデックス x でフィボナッチを計算するために最後の 2 つの数値を返すようにする方法を教えてください。ありがとう！

    def fastFib(x: Long ): Long = {
      def fast(x:Long , a:Long, b:Long):Long = 
      if (x<=0) a+b 
      else fast(x-1,b,a+b)
      if (x<2) 1 
      else fast(x-2,0,1)
   }

Answer 1

中間結果をキャッシュできるので、同じ結果を 2 回再計算することはありません

ここにコードがあります

//this supposed to contains all the value when initialized
//initialized with 0 for all value
val cache = Array [Int] (101);//0 to 100
cache(1)==1;//initial value
cache(2)=1;//initial value

def fibonacciCache(n:Int) : Int = {
  if (n>100)
  {
      println("error");
      return -1;
  }

  if (cache(n)!=0)//means value has been calculated
     return cache(n);
  else
  {
    cache(n)=fibonacciCache(n-1)+fibonacciCache(n-2);
    return cache(n);    
  }
}

それが役立つことを願っています