テール再帰 - スカラ（その他の言語）

Question

テール再帰に関する質問があります。私が知っているように、テール再帰は、関数からの最後の再帰呼び出しが関数の結果を提供するときです。しかし、私はこのような関数を持っています

def func1(n: Int): Int = { 
    if (n > 100) { 
     n - 10 
    } 
    else { 
     func1(func1(n + 11)) 
    } 
} 

テール再帰ですか？たとえば、

func1(100) = func1(func1(111)) = func1(101) = 91 

したがって、最後の再帰呼び出しはfunc1（101）になり、末尾再帰が正しくなるように結果を出力する必要がありますか？私は少し混乱しています。ありがとうございました！

Answer 1

テール再帰的ではありません。あなたはこのように見えるようにコードを書き換えることができます：

def func1(n: Int): Int = { 
    if (n > 100) { 
     n - 10 
    } 
    else { 
     val f = func1(n + 11) 
     func1(f) 
    } 
} 

あなたは尾の位置にない6行目の関数func1への呼び出しがあることがわかります。

Answer 2

いいえ、あなたの例は末尾再帰のケースではありません。

func1(func1(n + 11))は、非線形再帰（特にネストされた再帰）のケースです。

テール再帰は、直ちに反復（ループ）に変換できる特殊なケースです。これは簡単な最適化を可能にするため興味深いです。

あなたの場合、内部関数の呼び出しは関数の最後の操作ではありません（外部関数への呼び出しが保留されています）ので、末尾再帰はありません。

Answer 3

簡単に確認できる方法は、試してみることです。 @ tailrecアノテーション（import scala.annotation.tailrec）は、メソッドが末尾再帰型でない場合、コンパイル時エラーを返します。

これは、テール以外の位置で再帰呼び出しがあるため、これは末尾再帰的ではありません。

あなたの関数に2つの再帰呼び出しがあります。一つは末尾にあり、もう一つはメソッドの最後の呼び出しですが、もう一つはその呼び出しへの入力です。次の呼び出し。テールポジションで1つの再帰呼び出しを行うだけでは不十分です。すべての再帰呼び出しはテールコールでなければなりません。

Answer 4

実際、テール再帰メソッドは結果自体または次の呼び出しを返すメソッドです。アルゴリズムを次のように書き直すことができれば、それは尾を再帰的にすることができます。

trait Recursive[R] { 
    def oneIteration: Either[R, Recursive[R]] 
} 

object Recursive { 
    def interpret[R](fn: Recursive[R]): R = { 
    var res: Either[R, Recursive[R]] = Right(fn) 
    while(res.isRight) { 
     res = res.right.get.oneIteration 
    } 
    res.left.get 
    } 
} 

object Factorial extends App { 
    def factorial(acc: BigDecimal, n: Int): Recursive[BigDecimal] = new Recursive[BigDecimal] { 
    override def oneIteration(): Either[BigDecimal, Recursive[BigDecimal]] = { 
     if(n == 1){ 
     Left(acc) 
     } 
     else { 
     Right(factorial(acc * n, n - 1)) 
     } 
    } 
    } 

    val res = Recursive.interpret(factorial(1 , 5)) 
    println(res) 
}