CODEWITHSUNDEEP
scalarecursionstack-overflow
Brice
Brice

Reputation: 345

Scala newbie: recursion and stackoverflow error

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?

Upvotes: 14

Views: 7284

Answers (4)

Jens Nyman
Jens Nyman

Reputation: 1216

Here is an alternative to James Iry's answer, with the same behaviour:

def rangeRecursive(start: Int, end: Int): List[Int] = {
  def inner(start : Int) : Stream[Int] = {
      if (end < start) Stream.empty
      else start #:: inner(start + 1)
  }

  inner(start).toList
}

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

This does not throw a StackOverflowError because the Stream.cons-operator (#::) stores the tail by reference. In other words, the Stream elements are not computed until stream.toList is invoked.

In my opinion, this is more readable than the accumulator pattern because it most closely resembles the naive initial algorithm (just replace :: by #:: and Nil by Stream.empty). Also, there is no need for accum.reverse, which could easily be forgotten.

Upvotes: 1

James Iry
James Iry

Reputation: 19367

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.

Upvotes: 4

Emil L
Emil L

Reputation: 21091

If you rewrite the above so that it is tail recursive the compiler will optimize the code into a while loop. Addititonally you can use the @tailrec annotation to get an error when the method it is annotating is not tail recursive. Thus enabling you to know "when you got it right".

Upvotes: 1

jqno
jqno

Reputation: 15520

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.

Upvotes: 17

Related Questions