【Scala】Scala 入門 - フィボナッチ数列

再帰プログラミング

• 再帰関数を利用したプログラミングということでフィボナッチ数列をかいてみる

コード① - なりに書いてみる

object Fibonacci {

  def main(args: Array[String]): Unit = {
   printExecutionTime(println(fibo(100)))
  }

  def fibo(n: Int): Int = n match {
    case 1 => 1
    case 2 => 1
    case n => fibo(n - 2) + fibo(n - 1)
  }

  def printExecutionTime(proc: => Unit) = {
    val start = System.currentTimeMillis
    proc
    println((System.currentTimeMillis - start) + "msec")
  }
}

実行結果①

かえってこない(笑)

Σヽ(ﾟДﾟ; )ﾉ ｱｯ となりました。そりゃ、そうだ。オーダーもフィボナッチ数列になるんだもの。

コード② - 末尾再帰にする

object Fibonacci {

  def main(args: Array[String]): Unit = {
    printExecutionTime(println(fibo(100)))
  }

  def fibo(n: Int): Int = {
    def fibo2(a: Int, b: Int, count: Int): Int = count match {
      case 0 => a
      case 1 => b
      case count => fibo2(b, a + b, count - 1)
    }

    fibo2(1, 1, n)
  }

  def printExecutionTime(proc: => Unit) = {
    val start = System.currentTimeMillis
    proc
    println((System.currentTimeMillis - start) + "msec")
  }
}

実行結果②

-1869596475
228msec

結果は出たが、、、うん。

コード③ - Long にする

object Fibonacci {

  def main(args: Array[String]): Unit = {
    printExecutionTime(println(fibo(100)))
  }

  def fibo(n: Int): Long = {
    def fibo2(a: Long, b: Long, count: Int): Long = count match {
      case 0 => a
      case 1 => b
      case count => fibo2(b, a + b, count - 1)
    }

    fibo2(1, 1, n)
  }

  def printExecutionTime(proc: => Unit) = {
    val start = System.currentTimeMillis
    proc
    println((System.currentTimeMillis - start) + "msec")
  }
}

実行結果③

1298777728820984005
262msec

やっと出ました。長い道のりでしたが、勉強になりました。

末尾再帰になっているかチェックするアノテーション

@tailrec アノテーションをつけると、末尾再帰になっているかどうかをコンパイルのタイミングでチェックしてくれます。

@tailrec
  def fibo(n: Int): Int = n match {
    case 1 => 1
    case 2 => 1
    case n => fibo(n - 2) + fibo(n - 1)
  }

とするとコンパイルのときに怒られます。

Error:(16, 27) could not optimize @tailrec annotated method fibo: it contains a recursive call not in tail position
    case n => fibo(n - 2) + fibo(n - 1)

感想

• パターンマッチは、特異値の処理が書きやすくて良いですね。

• 末尾再帰、全然意識したことなかったので、勉強になりました。

  • 言語仕様として、コンパイルのタイミングでチェックできるのも素晴らしい。

参考ページ

• Scalaで再帰プログラミング

• Scala @tailrecメモ(Hishidama's Scala @tailrec Memo)