mog project: Scala: Fibonacci Number Calculation with Tail Recursion

2.12.2015

Scala: Fibonacci Number Calculation with Tail Recursion

Scala: 末尾再帰でフィボナッチ数を求める

第４回 Functional Programming in Scala読書会＠渋谷 - connpass でも練習問題として登場したので復習。

再帰なし - O(n)

まずは手続き型っぽい(Scala っぽくない)書き方で書いてみる。

def fib(n: Int): Int = {
  val a = Array.fill(math.max(2, n + 1))(0)
  a(1) = 1
  for (i <- 2 to n) {
    a(i) = a(i - 1) + a(i - 2)
  }
  a(n)
}

scala> (0 to 10).map(fib)
res0: scala.collection.immutable.IndexedSeq[Int] = Vector(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55)

n 番目のフィボナッチ数を求めるために必ずしも全てのフィボナッチ数をメモする必要はない。
直近2つだけを保持すればよい。

def fib(n: Int): Int = {
  var a = 0
  var b = 1
  for (i <- 1 to n) {
    val next = a + b
    a = b
    b = next
  }
  a
}

再帰バージョン - O(n)

上記の2個目のアイデアから再帰関数を導くことができる。

def fib(n: Int): Int = {
  @annotation.tailrec
  def loop(n: Int, a: Int, b: Int): Int =
    if (n <= 0)
      a
    else
      loop(n - 1, b, a + b)
  loop(n, 0, 1)
}

再帰バージョン - O(log(n))

行列累乗のテクニックを使って計算量を削減する。これも再帰で書けた。

def fib(n: Int): Int = {
  @annotation.tailrec
  def loop(n: Int, a: Int, b: Int, c: Int, d: Int, e: Int, f: Int): Int =
    if (n == 0)
      b
    else if ((n & 1) == 1)
      loop(n >> 1, a*d+b*e, b*d+c*e, b*e+c*f, d*d+e*e, d*e+e*f, e*e+f*f)
    else
      loop(n >> 1, a, b, c, d*d+e*e, d*e+e*f, e*e+f*f)
  loop(n, 1, 0, 1, 1, 1, 0)
}

scala> (0 to 10).map(fib)
res20: scala.collection.immutable.IndexedSeq[Int] = Vector(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55)

公式の正答例は References 参照。

Stream を使ったワンライナーなどは過去のエントリを参照。

mog project: Scala: Find Fibonacci Numbers Using Matrix Multiplication

References

fpinscala/GettingStarted.scala at master · fpinscala/fpinscala

mog project