CODEWITHSUNDEEP
stringscalarecursiontail-recursion
jsh6303
jsh6303

Reputation: 2040

Why do this recursive function fails with stack overflow? How can I improve it?

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

Upvotes: 1

Views: 229

Answers (3)

elm
elm

Reputation: 20415

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.

Upvotes: 0

Kevin Wright
Kevin Wright

Reputation: 49705

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.

Upvotes: 3

flavian
flavian

Reputation: 28511

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

Upvotes: 3

Related Questions