はじめに

以前投稿した記事「Scalaハンズオンで学んだ関数型プログラミング」で紹介したコードではスタックオーバーフローを起こしてしまうので、末尾再帰を使いましょうという話をちらっとさせていただきました。本記事では、末尾再帰についての補足説明をいたします。

お題

フィボナッチ数列のN番目の数値を求めるメソッド
※フィボナッチ数列とは？
フィボナッチ数列のN番目の数値はN-2番目の数値とN-1番目の数値の和となる。
なお、1番目と2番目の数値は1とする。

前回の方法で解く

※Int型で収まらなくなる気がしたので、諸々をLong型に変えてあります。

コード

1番目と2番目の数値は1, それ以外の数値は直前の2数（n-1番目の数とn-2番目の数）を足すという実装をしました。

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

10番目など再帰呼び出しの回数が少なければ問題がないのですが、回数が増えていくとスタックオーバーフローを起こしたり、OutOfMemoryErrorが発生したりするようです。

実行結果

私も試しに100番目の数を求めようと関数を実行してみました。
もはやエラーも発生せず、音沙汰なし。
JVMにビンタをしましたが、目を覚ましませんでした。

末尾再帰を使う

末尾再帰とは

関数を再帰呼び出しするときは、再帰関数の末尾で呼び出しましょうねということです。
以下のコードでは、関数gが自身の最後の処理で関数gを呼び出していることがわかります。
末尾再帰を使うことで、コンパイラが再帰関数をwhile式として最適化してくれるそうです。

Scalaで末尾再帰をつかう

Scalaで末尾再帰を使うときは、関数に@scala.annotation.tailrecアノテーションをつけましょう。
末尾再帰になっていなかったらコンパイルエラーにしてくれるという優れものです。

こういう風に組み立てるとやりやすいかもと思ったこと

末尾再帰の実装では、計算の途中経過（コレクションなど)を引数として与えるとうまく関数の定義ができそう。
今回の例では、計算の途中経過として、N-1番目とN-2番目の数値を引数に詰め込みました。

コード

def f(n: Long): Long = {
  /**
    * フィボナッチ数列m番目の数値を求める関数
    * m => 今求めようとしている数値が数列の何番目かを表す
    * a => m-2番目の値
    * b => m-1番目の値
    */
  @scala.annotation.tailrec
  def g(m: Long, a: Long = 0, b: Long= 0): Long = {
    // 今求めるべきは2つ前の数と1つ前の数の和
    val result = (a, b) match {
      case (0, 0) => 1
      case _ => a + b
    }
    if (m == n)  now else g(m + 1, b, result)
  }
  g(1)
}

実行結果

3736710778780434371という結果が戻ってきました。もはや正しいのかが分からなくて、ぐぐりましたが、正解でした。

さいごに

正直、関数型プログラミングのハンズオンを受けたときは、「これ、実務で使うの？」って思いました。
今回は、そもそも末尾再帰って何という話だったので平易な例になりましたが、実際に「プライベートで」プロダクトコードとして書いた末尾再帰の例について紹介したいと思います。