为什么这个scala并置函数不是递归的？

我想写一个函数重复（s：String，n：Int）将连接字符串sn时间并返回它，但由于某种原因，我没有得到正确的结果，并得到一个错误，它不是尾递归，并且我在逻辑上难以理解为什么这不是尾递归。为什么这个scala并置函数不是递归的？

递归是否必须在连接完成之前进行处理？我将如何解决这个问题？使递归重复（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：我这样做主要是为了练递归，而不是为了得到优化代码

来源

2016-09-20 Maribov

这并不是尾递归，因为递归调用'repeat'之后，还有更多的工作留在返回前做的，也就是'S + ...' –

是微不足道的看看你是否以函数形式写入：'plus（s，repeat（s，minus（n，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

来源

2016-09-20 21:29:10 pamu

线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) 
    }

来源

2016-09-20 21:40:09

为什么这个scala并置函数不是递归的？

回答

相关问题