CODEWITHSUNDEEP
javascala
Dhana Krishnasamy
Dhana Krishnasamy

Reputation: 2176

Scala StackOverflowError while Java can handle it

I am leaning to program in Scala and came across this problem where Scala code throws StackOverflowErorr while similar implementation in Java can go a bit more before throwing the same error

  def recursiveSum(args: Int*): Int = {
    if (args.length == 0) 0
    else
      args.head + recursiveSum(args.tail: _*)

  }                                               

  recursiveSum(5000 to 15000: _*)

The error i get is

    java.lang.StackOverflowError
//|     at scala.collection.Parallelizable$class.$init$(Parallelizable.scala:20)
//|     at scala.collection.AbstractTraversable.<init>(Traversable.scala:105)
//|     at scala.collection.AbstractIterable.<init>(Iterable.scala:54)
//|     at scala.collection.AbstractSeq.<init>(Seq.scala:40)
//|     at scala.collection.immutable.Range.<init>(Range.scala:44)
//|     at scala.collection.immutable.Range$Inclusive.<init>(Range.scala:330)
//|     at scala.collection.immutable.Range$Inclusive.copy(Range.scala:333)
//|     at scala.collection.immutable.Range.drop(Range.scala:170)
//|     at scala.collection.immutable.Range.tail(Range.scala:196)
//|     at scala.collection.immutable.Range.tail(Range.scala:44)
//|     at Loops$$anonfun$main$1.recursiveSum$1(Loops.scala:11)
//|     at Loops$$anonfun$main$1.recursiveSum$1(Loops.scala:11)
//|     at Loops$$anonfun$main$1.recursiveSum$1(Loops.scala:11)
//|     at Loops$$anonfun$main$1.recursiveSum$1(Loops.scala:11)
//|     at Loops$$anonfun$m
//| Output exceeds cutoff limit.

The java code is 

static int recursiveSum(int... arg) {
        if (arg.length == 0)
            return 0;
        else
            return arg[0] + recursiveSum(Arrays.copyOfRange(arg, 1, arg.length));
    }

    public static void main(String[] args) {
        System.out.println(recursiveSum(range(5000, 15000)));
    }

    private static int[] range(int i, int j) {
        int list[] = new int[j - i + 1];
        int idx = 0;
        for (int s = i; s <= j; s++)
            list[idx++] = s;
        return list;
    }

Why doesn't Scala's tail recursion optimization help? How come Java can handle (Java could not handle more than 15000 say 16000 as well )?

They are run on same eclipse ide with default stack size of java 7 on desktop machine.

Upvotes: 5

Views: 340

Answers (2)

WestCoastProjects
WestCoastProjects

Reputation: 63191

Your function is not formatted properly for tail recursion. You can verify this by (attempting to ) add the @tailrec annotation.

scala> import annotation.tailrec
import annotation.tailrec

scala> @tailrec  def recursiveSum(args: Int*): Int = {
     |     if (args.length == 0) 0
     |     else
     |       args.head + recursiveSum(args.tail: _*)
     |
     |   }
<console>:11: error: could not optimize @tailrec annotated method recursiveSum: it contains a recursive call not in tail position
             args.head + recursiveSum(args.tail: _*)

                   ^

Here is a working solution:

import annotation.tailrec
def recursiveSum(args: Int*): Int = {
  @tailrec  def recursiveSumInternal(sum : Int,  args: Int*): Int = {
      if (args.length == 0) 
          sum
      else
          recursiveSumInternal(sum+args.head, args.tail: _*)
   }
   recursiveSumInternal(0, args: _*)
 }

 recursiveSum(5000 to 15000 : _*)

Upvotes: 2

Todd
Todd

Reputation: 31710

This isn't tail recursive. In order for the function to be tail recursive the very last statement (the tail) in the function needs to be the recursive call. In your case, it might look like it is, but if you annotate your function with the @tailrec annotation, you'll see that it isn't. In fact, your last statement is an addition, not the recursive call.

If you rewrite your function to use an accumulator, you'll be able to do a tail recursive version...

def recursiveSum(args: Int*): Int = {
    @tailrec
    def sumAccumulator(sum: Int, args: Int*): Int = {
        if(args.length == 0) sum
        else sumAccumulator(sum + args.head, args.tail: _*)
    }
    sumAccumulator(0, args: _*)
}

recursiveSum(5000 to 15000: _*)

Upvotes: 7

Related Questions