@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
.