Scala - Tail Recursion 末尾再帰関数

Tail recursion

tail recursion(末尾再帰)とは、関数の最後のアクションが再帰呼び出しであるときに使われる用語です。
最大の特徴として、コンパイラが該当の再帰を最適化して、スタックオーバーフローのリスクを軽減することが挙げられています。

通常の再帰処理

def factorial(n: Int): Int = {
  if (n <= 1) 1
  else n * factorial(n - 1)
}

関数が自身を呼び出す際に、それまでの計算の状態(local変数やパラメータ)をスタック領域に保存します。
再起が深くなり、スタックが限界を超えるとスタックオーバーフローが発生し、プログラムがクラッシュしてしまいます。

item	descritpion
使い所	シンプルなアルゴリズムや浅い再帰呼び出しで適している
リスク	深い再帰ではスタックオーバーフローのリスクがある
適応例	短いリストの操作、単純な計算問題

末尾再帰処理

import scala.annotation.tailrec

def factorial(n: Int): Int = {
  @tailrec // scalaでは、`@tailrec`を付与することでコンパイラに末尾再帰を確認させることができます。
  def factorialTailrec(x: Int, accumulator: Int): Int = {
    if (x <= 1) accumulator
    else factorialTailrec(x - 1, x * accumulator)
  }

  factorialTailrec(n, 1)
}

関数の最後のアクションが自身の再帰呼び出しであり、その呼び出しの結果が直接返されます。
末尾再帰最適化をサポートする言語では、これをループに変換して、新しいスタックフレームの生成を防ぎます。
結果として、メモリ使用量が大幅に減少し、スタックオーバーフローのリスクが軽減されます。

item	descritpion
使い所	深い再帰やパフォーマンスが重要な場合に適している
利点	スタックオーバーフローのリスクが軽減され、効率的なループに最適化される
適応例	大規模なデータセット、複雑な計算問題

Sample code

商品の在庫管理を想定しているものです。
各種品には、在庫数がる、特定の物量が要求された場合にその要求を満たすことができるかシュミレートしています。

import scala.annotation.tailrec

case class Product(name: String, quantityInStock: Int)

def canFulfillOrder(products: List[Product], quantityRequired: Int): Boolean = {
  @tailrec
  def checkProducts(products: List[Product], quantityRemaining: Int): Boolean = products match {
    case Nil => quantityRemaining <= 0
    case Product(_, quantityInStock) :: tail =>
      if (quantityInStock >= quantityRemaining) true
      else checkProducts(tail, quantityRemaining - quantityInStock)
  }

  checkProducts(products, quantityRequired)
}

val products = List(Product("Widget", 10), Product("Gadget", 5), Product("Thing", 3))
println(canFulfillOrder(products, 15)) // true
println(canFulfillOrder(products, 20)) // false

参考文献

Scala & Functional Programming Essentials | Rock the JVM
Programming Scala, 3rd Edition