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

Question

我正在尝试编写一个函数 repeat(s: String, n: Int) ，它将连接字符串 s n 次并 return 它，但由于某种原因我没有得到正确的结果并且我得到一个错误，它不是尾递归的，我很难从逻辑上理解为什么这不是尾递归的。

是否需要递归处理才能完成拼接？我将如何解决这个问题？使递归 repeat(s+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 + 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)
  }

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

Why is this scala concatenation function not tail recursive?

scala

recursion

tail-recursion