このスカラー連結関数はなぜテール再帰的ではないのですか？

Question

文字列snを連結して返す関数repeat（s：String、n：Int）を作成しようとしていますが、何らかの理由で正しい結果が得られず、尾の再帰的な、私は論理的に尾の再帰的ではない理由を把握するのに苦労している。

連結が完了する前に再帰処理が必要ですか？どうすれば問題を解決できますか？再帰を繰り返す（s + s、n-1）ことはうまくいかないかもしれませんが、何回他の方法で実行するのか分かりません。

/** 
* Returns concatenated string s, concatenated n times 
*/ 
@annotation.tailrec 
def repeat(s: String, n: Int): String = n match { 
    case zero if (n == 0) => "" // zero repeats 
    case emptyString if (s == "") => throw new IllegalArgumentException("You must input a string") //no string exception 
    case fail if (n < 0) => throw new IllegalArgumentException("Cannot use a negative number") //throw exception 
    case last if (n == 1) => s 
    case concatenate => s + repeat(s, n-1) //tail-end recursion & concat. 
} 

PS：私は主にコードを最適化取得するために、とは対照的に、再帰を実践するためにこれをやっている

Answer 1

延期前のコールスタックの計算に依存してはならない末尾再帰現在の結果の場合は

def repeat(s: String, result: String, n: Int): Stringに以下の変更を加えてください。関数における注意結果はhelper内側機能

def repeat(s: String, n: Int): String = { 
     @annotation.tailrec 
     def helper(result: String, n: Int): String = n match { 
     case zero if (n == 0) => "" // zero repeats 
     case emptyString if (s == "") => throw new IllegalArgumentException("You must input a string") //no string exception 
     case fail if (n < 0) => throw new IllegalArgumentException("Cannot use a negative number") //throw exception 
     case last if (n == 1) => result 
     case concatenate => helper(s + result, n - 1) //tail-end recursion & concat. 
     } 
     helper(s, n) 
    } 

使用法を使用して実装する

@annotation.tailrec 
    def repeat(s: String, result: String, n: Int): String = n match { 
     case zero if (n == 0) => "" // zero repeats 
     case emptyString if (s == "") => throw new IllegalArgumentException("You must input a string") //no string exception 
     case fail if (n < 0) => throw new IllegalArgumentException("Cannot use a negative number") //throw exception 
     case last if (n == 1) => result 
     case concatenate => repeat(s, s + result, n-1) //tail-end recursion & concat. 
    } 

使用

scala> repeat("apple", "apple", 2) 
res3: String = appleapple 

クリーナー方法パラメータ

scala> repeat("apple", 1) 
res6: String = apple 

scala> repeat("apple", 2) 
res7: String = appleapple 

Answer 2

ラインs + repeat(s, n-1)はあなたが別の呼び出しの間の依存を避けるべきで末尾再帰を持たせたい場合は、答えは、関数の他の呼び出しに依存して機能します。例えば

：

def repeat(s: String, n: Int): String = { 

    @annotation.tailrec 
    def repeatIter(buffer: String, n: Int): String = { 
     n match { 
     case 0 => buffer 
     case _ => repeatIter(buffer + s, n - 1) 
     } 
    } 

    if (s.isEmpty || n < 0) throw new IllegalArgumentException("ERROR") 
    else repeatIter("", n) 
    }