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

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

書籍はこれ

Scala関数型デザイン&プログラミング―Scalazコントリビューターによる関数型徹底ガイド

まずは指定 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 前の最後の処理）で再起してないと言われた。

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

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

考え方を改めないといけないのだ。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

正しそうだ