Coursera Scale 1-7:再帰と末尾再帰

再帰
みんなはよく知らないで、1つの関数は直接あるいは間接的にそれ自身を呼び出して、再帰しました.簡単な階乗計算の例を見てみましょう.

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

以上のfactorialメソッドでは、n>1の場合、それ自体を呼び出す必要があります.これは典型的な再帰呼び出しです.n=5の場合、再帰的に呼び出されるプロセスは、概ね次のようになる.

factorial(5)
5 * factorial(4)
5 * (4 * factorial(3))
5 * (4 * (3 * factorial(2)))
5 * (4 * (3 * (2 * factorial(1))))
5 * (4 * (3 * (2 * 1)))
120

再帰アルゴリズムは、一般的には簡単で、人々の考え方に合っているが、呼び出しスタックを維持する必要があるため、効率が低く、呼び出し回数が多い場合、メモリを消費することが多い.したがって、プログラマーたちは、最初のバージョンを再帰的に実装し、最適化し、パフォーマンスを向上させるためにループに書き換えることが多い.尾は人々の目に入った.
テール再帰
最後の再帰とは、再帰呼び出しが関数の最後の文であり、その結果が直接返されることを意味します.これは特殊な再帰呼び出しです.再帰結果は常に直接返されるため、テール再帰はループに変換しやすいため、コンパイラは最適化しやすい.現在、多くのコンパイラはテール再帰に最適化されており、プログラマは手動でループに書き換える必要はありません.
上記の乗算関数は、再帰呼び出しの結果に追加の乗算計算があるため、再帰呼び出しのたびにスタックに残るデータを保持する必要があります.これを末尾再帰の方法に変更することができます.

def factorialTailrec(n: BigInt, acc: BigInt): BigInt = {
    if(n <= 1) acc
    else factorialTailrec(n-1, acc * n)
}

呼び出しプロセスを見ると、factorialTailrecの毎回の結果が直接返されます.やはりn=5を例にとると,今回の呼び出しプロセスは以下のようになる.

factorialTailrec(5, 1)
factorialTailrec(4, 5)  // 1 * 5 = 5
factorialTailrec(3, 20) // 5 * 4 = 20
factorialTailrec(3, 60) // 20 * 3 = 60
factorialTailrec(2, 120) // 60 * 2 = 120
factorialTailrec(1, 120) // 120 * 1 = 120120

以上の呼び出しは、呼び出し結果が直接返されるため、前の再帰呼び出しがスタックに残っているデータを破棄することができ、最後のデータを保持するだけでよい.これが尾再帰が最適化しやすい理由であり、その秘密兵器は上のaccである.これはアキュムレータ(accumulator、習慣的にアキュムレータと訳されていますが、必ずしも「加算」ではなく、任意の形式の蓄積でもよい)であり、前に呼び出された結果を蓄積するために使用され、前に呼び出されたデータを破棄することができます.
通常再帰を末尾再帰に書き換える
通常の再帰をテール再帰に書き換えるには、適切なアキュムレータを見つけることが重要です.次に、フィボナッチ数列を例に、アキュムレータを見つける方法を見てみましょう.フィボナッチ数列は、最初の2つが1で、3つ目から、それぞれが前の2つの和です.この定義は天然の再帰アルゴリズムであり,以下のようにする.

def fibonacci(n: Int): Int = {
  if (n <= 2) 1
  else fibonacci(n - 1) + fibonacci(n - 2)
}

やはりn=5を例に、その計算過程を見ます.

fibonacci(5)
fibonacci(4) + fibonacci(3)
(fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))
((fibonacci(2) + fibonacci(1)) + 1) + (1 + 1)
((1 + 1) + 1) + 2
5

以上は明らかにテール再帰ではありませんが、アキュムレータを見つけてテール再帰に変更するにはどうすればいいですか?前の2つの合計が必要であるため、ここでは2つのアキュムレータが必要であり、小さいものがacc 1、大きいものがacc 2であると仮定し、次のものを計算する必要がある場合、acc 2を新しいacc 1'に割り当て、(acc 1+acc 2)をacc 2'に割り当て、スタックに古いデータを呼び出すと破棄される.以下に、このプロセスのデモを示します.
n
0
1
2
3
4
F(n)
0
1
1
2
3

   acc1  acc2        
         acc1'=acc2 acc2'=acc1+acc2    
                     acc1''=acc2' acc2''=(acc1'+acc2') acc1'''=acc2''        acc2'''=acc1''+acc2''

上記のプレゼンテーション手順に従って、コードを次のように書くことができます.

def fibonacciTailrec(n: Int, acc1: Int, acc2: Int): Int = {
  if (n < 2) acc2
  else fibonacciTailrec(n - 1, acc2, acc1 + acc2)
}

以上のコードは,再帰の結果を直接返すため,厳密な末尾再帰であり,n=5の場合,呼び出しプロセスは以下のようになる.

fibonacciTailrec(5,0,1)
fibonacciTailrec(4,1,1)
fibonacciTailrec(3,1,2)
fibonacciTailrec(2,2,3)
fibonacciTailrec(1,3,5)
5

上記の過程は単純な書き換え再帰の方法を実証するだけで、実際には、アキュムレータについては、より普遍的な法則があり、ここでは深く紹介しない.上記の一般再帰とテール再帰の効率を比較すると,完全なコードは以下の通りである.

def fibonacci(n: Int): Int = {
  if (n <= 2) 1
  else fibonacci(n - 1) + fibonacci(n - 2)
}

def fibonacciTailrec(n: Int, acc1: Int, acc2: Int): Int = {
  if (n < 2) acc2
  else fibonacciTailrec(n - 1, acc2, acc1 + acc2)
}

val list = List(20, 30, 40)
val sw = new Stopwatch
for (num <- list) {
  println("n = " + num)
  sw.start("Normal")
  val ret = fibonacci(num)
  println("F(n) = " + ret)
  sw.stop()

  sw.start("Tail")
  val retTail = fibonacciTailrec(num, 0, 1)
  println("FT(n) = " + retTail)
  sw.stop()
  println(sw.prettyPrint())
  println()
  sw.reset()
}

上記のコードは,ある実行出力の結果は以下の通りである(プロセッサ1.8 GHz Intel Core i 5).

n = 20
F(n)  = 6765
FT(n) = 6765
Total time elapsed: 2(ms)
-------------------------------------
 (ms)    (%)   Task name
    2  100.00  Normal
    0    0.00  TailRec
-------------------------------------

n = 30
F(n)  = 832040
FT(n) = 832040
Total time elapsed: 3(ms)
-------------------------------------
 (ms)    (%)   Task name
    3  100.00  Normal
    0    0.00  TailRec
-------------------------------------

n = 40
F(n)  = 102334155
FT(n) = 102334155
Total time elapsed: 396(ms)
-------------------------------------
 (ms)    (%)   Task name
  396  100.00  Normal
    0    0.00  TailRec
-------------------------------------

完全なルーチン、TailRecursionを参照
Scalaの末尾再帰サポート
サポート
Scalaは形式的に厳格なテール再帰を最適化し,厳格なテール再帰に対しては安心して使用でき,性能の問題を心配する必要はない.厳格な末尾再帰であるか否かについては、自己判断ができない場合は、Scalaが提供する末尾再帰表記@scalaを用いることができる.annotation.tailrec、この記号はテール再帰を識別する以外に、コンパイラが関数が本当にテール再帰しているかどうかをチェックすることが重要です.そうでない場合、次のコンパイルエラーが発生します.

could not optimize @tailrec annotated method fibonacci: it contains a recursive call not in tail position

制限
JVMの制約により,テール再帰の深い階層の最適化が困難であるため,Scalaのテール再帰の最適化は限られており,形式的に非常に厳しいテール再帰のみを最適化することができる.すなわち,以下の状況は最適化の列にない.
最後の再帰が直接呼び出しではなく、関数値を通過する場合.たとえば、上記の乗算の末尾再帰バージョンでは、直接呼び出すのではなくfuncに関数を割り当てるように書き換えると、コンパイラは末尾再帰とは思いません.

//call function value will not be optimized
val func = factorialTailrec _
def factorialTailrec(n: BigInt, acc: BigInt): BigInt = {
if(n <= 1) acc
else func(n-1, acc*n)
}

間接再帰は間接再帰を最適化されず、直接自身を呼び出すのではなく、他の関数によって最終的に自身を呼び出す再帰を指す.以下に示す.

//indirect recursion will not be optimized
def foo(n: Int) : Int = {
if(n == 0) 0;
bar(n)
}
def bar(n: Int) : Int = {
foo(n-1)
}

Reference
scalass.com/zh/article/tail-recursion.html