为什么这个scala串联函数不是尾递归的? [英] Why is this scala concatenation function not tail recursive?

问题描述

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

I'm trying to write a function repeat(s: String, n: Int) that will concatenate string s n times and return it, but for some reason I am not getting the correct results and am getting an error that it is not tail recursive, and I'm having trouble grasping logically why this wouldn't be tail recursive.

在串联完成之前是否必须处理递归?我将如何解决问题?使递归 repeat(s+s, n-1) 不起作用，因为它会递归 s 太多次，但我不确定还有什么其他方法可以做到.

Does the recursion have to process before the concatenation can be completed? How would I solve the problem? Making the recursion repeat(s+s, n-1) wouldn't work because it would recurse s too many times, but i'm not sure what other way to do it.

/**
 * 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:我这样做主要是为了练习递归，而不是为了获得优化的代码

ps: i'm doing this mostly to practice recursion as opposed to in order to get optimized code

推荐答案

在尾递归的情况下，当前结果不应依赖于延迟的先前调用堆栈计算

In case of tail recursion current result should not depend on deferred previous call stack computation

对您的函数 def repeat(s: String, result: String, n: Int): String 进行以下更改.注意函数参数中的结果

Make the following change to your function def repeat(s: String, result: String, n: Int): String. Notice result in the function parameters

@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内部函数实现更简洁的方式

Cleaner way to implement using helper inner function

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

这篇关于为什么这个scala串联函数不是尾递归的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！