技術をかじる猫

適当に気になった技術や言語、思ったこと考えた事など。

Scala 関数型デザイン&プログラミング:Exercize2.1

真面目にやろうかと思った。

書籍はこれ

まずは指定 N 番目のフィボナッチ数計算関数を tail call recursive (末尾再帰)な関数で実装しろとのこと。
まず単純にフィボナッチ数列の実装をしてみる。

Wikipedia 先生 にお越しいただこう。

フィボナッチ数 - Wikipedia

object Exercise2_1 extends App {

  def fib(n: Long): Long = n match {
    case 0 => 0
    case 1 => 1
    case _ => fib(n - 2) + fib(n - 1)
  }

  for (i <- (0 to 10)) {
    println(s"$i : ${fib(i)}")
  }
}

これが末尾再帰かを判定するには、Scala の「scala.annotation.tailrec」を使えばいい。

  import scala.annotation.tailrec

  @tailrec
  def fib(n: Long): Long = n match {
    case 0 => 0
    case 1 => 1
    case _ => fib(n - 2) + fib(n - 1)
  }

  for (i <- (0 to 10)) {
    println(s"$i : ${fib(i)}")
  }

コンパイルすると、下記のエラーだ

[info] Compiling 1 Scala source to /Users/xxxx/Documents/projects/scala-function/part1/target/scala-2.11/classes...
[error] /Users/xxxx/Documents/projects/scala-function/part1/src/main/scala/Excercise2_1.scala:24: could not optimize @tailrec annotated method fib: it contains a recursive call not in tail position
[error]     case _ => fib(n - 2) + fib(n - 1)

it contains a recursive call not in tail position 最後の処理(return 前の最後の処理)で再起してないと言われた。

こう読み替えるとわかりやすいが、再起した結果に何らかの処理を加えてはならないということだ。

で、1時間位悩んだわけなのだが、結論から行こう。

考え方を改めないといけないのだ。n は「n 番目の計算結果を得る」という考え方をするのではなくて、「後 n 回計算する」と考える。
その上で、引数を考えると、下記で計算できるのではないだろうか?

後 5 回計算すると考えた時、

  1. 残 5 回、初期値 0
  2. 残 4 回、初期値 1 こう考えれば初期2回は特別なんだと考えて良さそうだ。
  3. 残 3 回、2 回目の値 + 1回目の値
  4. 残 2 回、3 回目の値 + 2回目の値 = (2 回目の値 + 1回目の値) + 2回目の値
  5. 残 1 回、4 回目の値 + 3回目の値 = ((2 回目の値 + 1回目の値) + 2回目の値) + (2 回目の値 + 1回目の値)

これを一般化して考えると、

  • 残り 1 回 = 前回 + 前々回
  • 残り 2 以上 = カウント減算、前回 + 前々回、前回

これを愚直に再起に書くとこうなる。普通に tailrec でコンパイル可能だ。

    @tailrec
    def fib(n: Long, n1: Long, n2: Long): Long = {
      n match {
        case 1 => n1 + n2
        case _ => sub(n - 1, n1 + n2, n1)
      }
    }

しかし、計算回数 0 回目、1回目という特殊ケースもあるので、事前にその答えを設定する。

  def fib(n: Long): Long = {

    @tailrec
    def sub(n: Long, n1: Long, n2: Long): Long = {
      n match {
        case 1 => n1 + n2
        case _ => sub(n - 1, n1 + n2, n1)
      }
    }

    n match {
      case 0 => 0
      case 1 => 1
      case _ => sub(n - 1, 1, 0)
    }
  }

こうなるはず。

試してみようか

  for (i <- (1 to 20)) {
    println(s"$i : ${fib(i)}")
  }

実行

$ sbt run
[info] Loading global plugins from /Users/xxxx/.sbt/0.13/plugins
[info] Set current project to sample (in build file:/Users/azalea/Documents/projects/scala-function/part1/)
[info] Compiling 1 Scala source to /Users/xxxx/Documents/projects/scala-function/part1/target/scala-2.11/classes...
[info] Running Excercise2_1 
1 : 1
2 : 1
3 : 2
4 : 3
5 : 5
6 : 8
7 : 13
8 : 21
9 : 34
10 : 55
11 : 89
12 : 144
13 : 233
14 : 377
15 : 610
16 : 987
17 : 1597
18 : 2584
19 : 4181
20 : 6765

正しそうだ