コップ本の第16章『リストの操作』で、Listのような再帰的なデータ構造を扱う方法として、分割統治という原則が紹介されている。その説明は以下の通り。

リストを対象とする多くのアルゴリズムは、パターンマッチを使って最初に入力リストを単純なケースに分割する。これが原則の中の分割（devide）の部分である。次に、個々のケースのための結果値を作る。結果値が空でないリストなら、その一部は同じアルゴリズムを再帰的に呼び出すことによって組み立てられる。これが原則の統治（conquer）の部分である。

この中で分割統治の原則に従って2つのリストを連結するappend関数（:::と同じことをやる関数）が紹介されていて、その中身はこんな感じ。

def append[T](xs: List[T], ys: List[T]): List[T] = 
  xs match {
    case List() => ys
    case x :: xs1 => x :: append(xs1, ys)
  }

という形なのですが、immutableなListを引数に取って、別のリストを作る方法がとても簡単にかけるな〜、と思っていた。

だけど、この方法で気にしなきゃいけないのが、引数のリストが大きい場合に、関数の再帰呼び出しに伴ってスタックメモリーを消費するとか、スタックフレームの生成コストとか、スタックオーバーフローの問題がある。

で、そうなると再帰呼び出しを行う場合には、末尾再帰し、Scalaコンパイラーに再帰呼び出しの最適化を行ってもらうという話になる。

で、前置きが長くなったけど、この投稿の目的。。末尾再帰によってどのくらい効率的になるもんか、、、というのを比べてみた。

ということで、例として、素数を見つける処理を非末尾再帰版と末尾再帰版で比較してみた。

まずは非末尾再帰版。

def findPrimeNumbers(n: Int): List[Int] = findPrimeNumbers(Range(2, n + 1).toList)

def findPrimeNumbers(numbersToSearch: List[Int]):List[Int] = numbersToSearch match {
  case Nil => Nil
  case n :: ns => n :: findPrimeNumbers(ns.filter(_ % n != 0))
}

scala> :paste
// Entering paste mode (ctrl-D to finish)

new scala.testing.Benchmark {
  def run() = findPrimeNumbers(10000)}.runBenchmark(10)
}.runBenchmark(10)

// Exiting paste mode, now interpreting.
warning: there were 1 deprecation warning(s); re-run with -deprecation for detailsfindPrimeNumbers: (n: Int)List[Int]
res0: List[Long] = List(122, 126, 126, 127, 160, 123, 121, 127, 73, 21)

一方で、末尾再帰版。

def findPrimeNumbersTailRecursively(n: Int): List[Int] = findPrimeNumbersTailRecursively(Range(2, n + 1).toList)

def findPrimeNumbersTailRecursively(numbersToSearch: List[Int]): List[Int] = {
  def findPrimeNumbersTailRecursively(xs:List[Int], ys:List[Int]):List[Int] = xs match {
    case Nil => ys.reverse
    case x :: xs1 => findPrimeNumbersTailRecursively(xs1.filter(_ % x != 0), x :: ys)
  }
  findPrimeNumbersTailRecursively(numbersToSearch, Nil)
}

scala> :paste
// Entering paste mode (ctrl-D to finish)

new scala.testing.Benchmark {
  def run() = findPrimeNumbersTailRecursively(10000)
}.runBenchmark(10)

// Exiting paste mode, now interpreting.

warning: there were 1 deprecation warning(s); re-run with -deprecation for details
findPrimeNumbersTailRecursively: (n: Int)List[Int]
res1: List[Long] = List(108, 44, 43, 42, 43, 43, 43, 42, 43, 53)

ということで、明らかに末尾再帰版の方が良かった。（引数を大きくすると非末尾再帰版の方はstackOverflowErrorも発生する）

当たり前と言えば当たり前なのだけど。。

でも、末尾再帰をするためには、上のコードを見てわかるように、コードが若干直感的じゃなくなる、というところがあったりする気がする。。。皆さんどうしてるのでしょうか。。