久しぶりのfib関数

先日、関数型まつりに参加した影響で、久しぶりにフィボナッチ数を求める関数でも書くか！と思って書き始めたら、再帰＋末尾最適化バージョンが一発でそらで書けず、過去に書いたコードを見て、「あー」となったので、その記録。

なんでも忘れるものですね...

単純なループバージョン

定義の通りに書いただけ

でも再帰を使ってないので、関数型っぽくない

def fib1(n: Int): BigInt =
  if n <= 1 then BigInt(n)
  else
    var a: BigInt = 0
    var b: BigInt = 1

    for (_ <- 2 to n)
      val n = a + b
      a = b
      b = n

    b

素直に再帰を使って書いたバージョン

これも定義通りに素直に書いただけ

def fib2(n: Int): BigInt =
  def loop(n: Int): BigInt =
    if n <= 1 then BigInt(n)
    else
      loop(n - 2) + loop(n - 1)

  loop(n)

でも、末尾最適化が効かないため、処理時間は爆増する

fib2(50)くらいで全然帰ってこなくなる

末尾最適化に対応したバージョン

過去のコードを見て書き写した...

ここでのloop関数の中でのcountは、単純な再帰バージョンでのインデックスではなく、カウントダウンするためのカウンター

accの中に、累積した値を持ち回り、計算完了時点（countがゼロになった時点）で、accを取得する

def fib3(n: Int): BigInt =
  @annotation.tailrec
  def loop(count: Int, acc: (BigInt, BigInt)): BigInt =
    if count <= 0 then acc._1
    else loop(count - 1, (acc._2, acc._1 + acc._2))

  loop(n, (0, 1))

これなら、fib3(50)は当然余裕で帰ってくる

カウンターが下がっていくのと逆に、引数で持ち回っているaccがどんどん累積されて増えていく、という感覚が掴めるか？というところがポイントですね