Scala Language
再帰

テール再帰

通常の再帰を使用すると、各再帰呼び出しは別のエントリを呼び出しスタックにプッシュします。再帰が完了すると、アプリケーションは各エントリを一度ポップダウンして戻らなければなりません。多くの再帰的な関数呼び出しがある場合、それは巨大なスタックで終わる可能性があります。

スカラは、再帰呼び出しを末尾に見つけた場合に自動的に再帰を削除します。注釈（ @tailrec ）を再帰関数に追加して、テールコールの最適化を確実に行うことができます。コンパイラは、再帰を最適化できない場合、エラーメッセージを表示します。

定期的な再帰

この例は、再帰呼び出しが行われたときに、関数が呼び出しが復帰した後に結果と関係がある乗算を追跡する必要があるため、末尾再帰ではありません。

def fact(i : Int) : Int = {
   if(i <= 1) i
   else i * fact(i-1)
}

println(fact(5))

パラメータを指定して関数を呼び出すと、スタックは次のようになります。

(fact 5)
(* 5 (fact 4))
(* 5 (* 4 (fact 3)))
(* 5 (* 4 (* 3 (fact 2))))
(* 5 (* 4 (* 3 (* 2 (fact 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1 (fact 0))))))
(* 5 (* 4 (* 3 (* 2 (* 1 * 1)))))
(* 5 (* 4 (* 3 (* 2))))
(* 5 (* 4 (* 6)))
(* 5 (* 24))
120

この例を@tailrecアノテーションしようとすると、次のエラーメッセージが表示されます。 could not optimize @tailrec annotated method fact: it contains a recursive call not in tail position

テール再帰

末尾再帰では、まず計算を実行してから、再帰呼び出しを実行して、現在のステップの結果を次の再帰ステップに渡します。

def fact_with_tailrec(i : Int) : Long = {
   @tailrec
   def fact_inside(i : Int, sum: Long) : Long = {
      if(i <= 1) sum
      else fact_inside(i-1,sum*i)
   }
   fact_inside(i,1)
}

println(fact_with_tailrec(5))

対照的に、テール再帰階乗のスタックトレースは次のようになります。

(fact_with_tailrec 5)
(fact_inside 5 1)
(fact_inside 4 5)
(fact_inside 3 20)
(fact_inside 2 60)
(fact_inside 1 120)

fact_insideへの呼び出しごとに同じ量のデータを追跡する必要があるのは、関数が単純に値を上に戻すためです。つまり、 fact_with_tail 1000000が呼び出されたとしても、 fact_with_tail 3と同じ量のスペースしか必要としません。これは、非テール再帰呼び出しでは当てはまりません。そのような大きな値はスタックオーバーフローを引き起こす可能性があります。

トランポリンによるスタックレス再帰（scala.util.control.TailCalls）

再帰関数の呼び出し中にStackOverflowErrorエラーが発生することは非常に一般的です。 Scala標準ライブラリは、ヒープオブジェクトと継続を使用してスタックのオーバーフローを回避し、再帰のローカル状態を格納するTailCallを提供します。

TailCallsのスカードからの2つの例

import scala.util.control.TailCalls._
    
def isEven(xs: List[Int]): TailRec[Boolean] =
  if (xs.isEmpty) done(true) else tailcall(isOdd(xs.tail))
    
def isOdd(xs: List[Int]): TailRec[Boolean] =
  if (xs.isEmpty) done(false) else tailcall(isEven(xs.tail))

// Does this List contain an even number of elements?
isEven((1 to 100000).toList).result

def fib(n: Int): TailRec[Int] =
  if (n < 2) done(n) else for {
    x <- tailcall(fib(n - 1))
    y <- tailcall(fib(n - 2))
  } yield (x + y)

// What is the 40th entry of the Fibonacci series?
fib(40).result