Scala newbie: recursion and stackoverflow error

Question

As a Scala newbie, I'm reading books, docs and try to solve problems found on http://aperiodic.net/phil/scala/s-99/ . It seems correct Scala code is based on immutable values (val) and on recursion rather than on loops and variables in order to make parallelism safer and to avoid need to use locks.

For example, a possible solution for exercise P22 ( http://aperiodic.net/phil/scala/s-99/p22.scala ) is :

// Recursive.
def rangeRecursive(start: Int, end: Int): List[Int] =
if (end < start) Nil
else start :: rangeRecursive(start + 1, end)

Of course this code is compact and looks smart but, of course, if the number of recursion is high, you'll face a StackOverflow error (rangeRecusrsive(1,10000) for example with no JVM tuning). If you look at the source of the built in List.range (https://github.com/scala/scala/blob/v2.9.2/src/library/scala/collection/immutable/List.scala#L1), you'll see that loops and vars are used.

My question is how to manage the influence of the Scala learning stuff which is promoting vals and recursion knowing that such code can break due to the number of recursion?

Answer 1

The nice thing about Scala is that you can easy your way into it. Starting out, you can write loops, and do more with recursion as you grow more comfortable with the language. You can't do this with the more 'pure' functional languages such as Clojure or Haskell. In other words, you can get comfortable with immutability and val, and move on to recursion later.

When you do start with recursion, you should look up tail call recursion. If the recursive call is the last call in the function, the Scala compiler will optimize this into a loop in bytecode. That way, you won't get StackOverflowErrors. Also, if you add the @tailrec annotation to your recursive function, the compiler will warn you if your function is not tail call recursive.

For example, the function in your question is not tail call recursive. It looks like the call to rangeRecursive is the last one in the function, but when this call returns, it still has to append start to the result of the call. Therefore, it cannot be tail call recursive: it still has to do work when the call returns.

Answer 2

Here's an example of making that method tail recursive. The @tailrec annotation isn't necessary, the compiler will optimize without it. But having it makes the compiler flag an error when it can't do the optimization.

scala> def rangeRecursive(start: Int, end: Int): List[Int] = {
    |   @scala.annotation.tailrec
    |   def inner(accum : List[Int], start : Int) : List[Int] = {
    |       if (end < start) accum.reverse
    |       else inner(start :: accum, start + 1)
    |   }
    |   
    |   inner(Nil, start)
    | }
rangeRecursive: (start: Int,end: Int)List[Int]

scala> rangeRecursive(1,10000)
res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,...

It uses a common technique called "accumulator passing style" where intermediate results are accumulated and passed to the next step in the recursion. The bottom most step is responsible for returning the accumulated result. In this case the accumulator happens to build its result backwards so the base case has to reverse it.