为什么这个scala连接函数不是尾部递归的？

Question

我试图编写一个函数repeat（s:String，n:Int），它将串接字符串s n次并返回它，但由于某种原因，我没有得到正确的结果，并且得到了一个错误，即它不是尾部递归的，我在逻辑上很难理解为什么它不是尾部递归的。

在连接完成之前，是否必须处理递归？我该如何解决这个问题？使递归重复（s，n-1）不起作用，因为它会递归s太多次，但我不确定还有什么其他方法可以做到。

/**
 * 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进行以下更改。注意函数参数中的结果

@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

使用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)
    }

用法

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

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

Answer 2

这一行重复（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)
  }