Scala で n 番目のフィボナッチ数を題材に再帰脳をつくる

「Scala 関数型デザイン＆プログラミング ―Scalazコントリビューターによる関数型徹底ガイド」（原書：Functional Programming in Scala）の第2章に出てくるフィボナッチ数列の練習問題で悩む人が多いようだ。再帰脳を身につけるのに良さそうなので、それを題材に再帰の考え方をメモっとく。

# n 番目のフィボナッチ数を計算する関数

下記のような定義は与えられて、これを末尾再帰で作れと言われる。

```scala
def fib(n: Int): Int = ???
```

これをいきなり解くのは難しいので、その考え方を順を追って説明してみる。

# フィボナッチ数列

フィボナッチ数ってそもそも何ってことを理解しよう。数式を理解せずとも具体例を書いてみよう。人間は具体例からパターンを捉えるのが得意だから、具体例を自分で書いてみると一気に理解が進むよ。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

前2つの数を足した結果が現在の数になるってことが数列からわかる。

# 0番目のフィボナッチ数

0番目のフィボナッチ数、つまり n = 0 のときのフィボナッチ数を考えてみる。

数列を眺めてみると0番目のフィボナッチ数は0らしいので、`fib(0) = 0` である。

再帰を考えるときは最小の例題から考える。「0番目のフィボナッチ数は0」と定義するしかないようなものは最小の例題である。このような最小の例題が終了条件になることが多い。

# 1番目のフィボナッチ数

1番目のフィボナッチ数、つまり n = 1 のときのフィボナッチ数を考えてみる。

数列を眺めてみると1番目のフィボナッチ数は1らしいので、`fib(1) = 1` である。

再帰を考えるときは最小の例題を考えたのち、最小の例題から5つくらいを具体的に考える。フィボナッチ数の難しさでもあるのだけど、これも「1番目のフィボナッチ数は1」と定義するしかない。

# 2番目・3番目・4番目・5番目のフィボナッチ数

5番目のフィボナッチ数までの具体例を書いてみると下記のようになる。

```
fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
```

ここで fib(5) ってどうやって計算するんだっけと考えてみる。「前2つの数を足した結果が現在の数」になるから、`fib(3) + fib(4) = fib(5)` となる。その考え方で上記を書き直してみると下記のようになる。

```
fib(0) = 0
fib(1) = 1
fib(2) = fib(0) + fib(1)
fib(3) = fib(1) + fib(2)
fib(4) = fib(2) + fib(3)
fib(5) = fib(3) + fib(4)
```

だいぶパターンが見えてきたんじゃないかな。ここで変数 n を導入して上記を書き直してみると下記のようになる。

```
fib(0) = 0
fib(1) = 1
fib(n) = fib(n - 2) + fib(n - 1) when n = 2
fib(n) = fib(n - 2) + fib(n - 1) when n = 3
fib(n) = fib(n - 2) + fib(n - 1) when n = 4
fib(n) = fib(n - 2) + fib(n - 1) when n = 5
```

そう、つまり、こういうことだ。

```
fib(0) = 0
fib(1) = 1
fib(n) = fib(n - 2) + fib(n - 1)
```

# n 番目のフィボナッチ数を計算する関数を定義する

パターンマッチをつかうとそのまま素直にかける。

```scala
def fib(n: Int): Int = n match {
  case 0 => 0
  case 1 => 1
  case n => fib(n - 2) + fib(n - 1)
}
```

実際に実行してみる。

```
scala> fib(0)
res0: Int = 0

scala> fib(1)
res1: Int = 1

scala> fib(2)
res2: Int = 1

scala> fib(3)
res3: Int = 2

scala> fib(4)
res4: Int = 3

scala> fib(5)
res5: Int = 5
```

# 末尾再帰じゃないということを認識してみる

数学的にはまったくもって問題ないのだけど、コンピューターで計算することを考えると末尾再帰にする必要がある。ということなのだけど、この関数が末尾再帰ではないことをまずは理解しよう。

再帰呼び出しの `fib(n - 2) + fib(n - 1)` が末尾再帰ではない。`fib(n - 2)` と `fib(n - 1)` の結果を加算するので再帰呼び出しの結果を待つ必要があるからだ。下記のように考えると `fib(4)` から `fib(0)` と `fib(1)` になる方向に計算されていることがわかる。n が大きくなれば1行が横に伸びていくことが想像できる。この1行の横の長さがスタックを消費するというように考えればいいかなと。

```
fib(4)
=> fib(2)          + fib(3)
=> fib(0) + fib(1) + fib(1) + fib(2)
=> 0      + 1      + 1      + fib(0) + fib(1)
=> 0      + 1      + 1      + 0      + 1
=> 3
```

# 末尾再帰を目指してみる

「前2つの数を足した結果が現在の数」なので、前2つの数から計算されるように考え直してみたい。つまり、`fib(0)` と `fib(1)` から `fib(4)` になる方向に計算するようにすると下記のようになる。

```
fib(0) => 0
fib(1) => 1
fib(2) => fib(0) + fib(1) => 0 + 1 => 1
fib(3) => fib(1) + fib(2) => 1 + 1 => 2
fib(4) => fib(2) + fib(3) => 1 + 2 => 3
fib(5) => fib(3) + fib(4) => 2 + 3 => 5
```

これは下記の構造になっている。`a+b` の部分が n 番目のフィボナッチ数になる。

```
fib(n) 0  1  1  2  3  5
n = 2  a  b  a+b
    3     a  b  a+b
    4        a  b  a+b
    5           a  b  a+b
```

下記のように n = 2 の結果を受けて、n = 3 を計算できる。

```
[n = 3]    [n = 2]
 a      <=  b
 b      <=  a + b
```

下記のような縦の関係が見える。

```
fib(n) 0  1  1  2  3  5
n = 2  a  b  a+b
          |  |
    3     a  b  a+b
             |  |
    4        a  b  a+b
                |  |
    5           a  b  a+b
```

# 末尾再帰で定義する

定義した関数を下記のように修正すると末尾再帰になる。前述の図をループに落とし込んだだけ。

```scala
def fib(n: Int): Int = n match {
  case 0 => 0
  case 1 => 1
  case n => {
    @annotation.tailrec
    def loop(i: Int, a: Int, b: Int): Int =
      if (i == n) a + b
      else loop(i + 1, b, a + b)

    loop(2, 0, 1)
  }
}
```

# もっと単純にしてみる

n = 0 と n = 1 が例外的な扱いになっているのがいただけない。さっきのテーブルを下記のように書き換えて、`a` の部分が n 番目のフィボナッチ数と考えてみたらどうだろう？

```
fib(n) 0  1  1  2  3  5  8  13
n = 0  a  b  a+b
    1     a  b  a+b
    2        a  b  a+b
    3           a  b  a+b
    4              a  b  a+b
    5                 a  b  a+b
```

定義した関数をさらに下記のように修正してみる。

```scala
def fib(n: Int): Int = {
  @annotation.tailrec
  def loop(i: Int, a: Int, b: Int): Int =
    if (i == n) a
    else loop(i + 1, b, a + b)

  loop(0, 0, 1)
}
```

いい感じだ。これでほぼ完成なのだけど、もう少しだけ単純化しよう。`i` はカウンターとして機能しているが計算には使用されていないので、n 回ループするだけなら下記のように書ける。

```scala
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)
}
```

これで解答ができあがった。

# まとめ

再帰脳になるには具体例を考えてパターンを見つけること。練習は必要だけどすぐに慣れるはず。

"How do I get to Carnegie Hall? Practice. Practice. Practice."