@annotation.tailrec
final def repeat(s: String, n: Int, ss: String = ""): String = {
if (n == 0) ss else repeat(s, n - 1, ss + s)
}
repeat("test", 5)
Why do this recursive function fails with stack overflow? How can I improve it?
-
01-10-2022 - |
문제
I am thinking of writing a recursive function in scala that concatenate the string for n times. My code is below:
def repeat(s: String, n: Int): String = {
if(n==1) s
else
s+repeat(s,n-1)
}
Is it possible that I did not use "+" properly? But the "+" is indeed a sign of concatenation, as I was originally trying
def repeat(s: String, n: Int): String = {
if(n==1) s
else
repeat(s+s,n-1)
}
That repeats my string 2^n times
해결책
다른 팁
Your first version is NOT tail recursive.
It has to call itself and then prepends s. For tail recursion the very last expression must be the self-call. This means it'll blow the stack for large values of n
The second version is tail recursive.
Put @annotation.tailrec
before both definitions, and the compiler will throw an error where it can't perform tail-call optimisation.
A simple approach that bypasses recursion,
def repeat(s: String, n: Int) = s * n
Hence,
scala> repeat("mystring",3)
res0: String = mystringmystringmystring
This function may be rewritten into a recursive form for instance as follows,
def re(s: String, n: Int): String = n match {
case m if (m <= 0) => ""
case 1 => s
case m => s + re(s,n-1)
}
Note the uses of +
and *
operators on String
.