Sign up ×

As a Scala newbie, I'm reading books, docs and try to solve problems found on . 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 ( ) 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 (, 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?

share|improve this question
Scala compiler is smart enough to make tail-recursive calls compiled in trampoolined tail recursion (JVM isn't support TCE), which will not leed to the stackoveflow. If you want to be sure, that your code is tail recursive, add @tailrec annotation to the method signature – om-nom-nom Jul 27 '12 at 10:53

4 Answers 4

up vote 8 down vote accepted

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.

share|improve this answer
Thanks, so the ultimate target is to make tail recursive functions, not just recursive functions, right? – Brice Jul 27 '12 at 11:15
@Brice As much as possible, yes. Sometimes it's not possible, but often, it is. In these cases, you get performance improvements, and you won't have to worry about stack overflows. – jqno Jul 27 '12 at 11:17

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)

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.

share|improve this answer

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

share|improve this answer

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

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


scala> rangeRecursive(1,10000)

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.

share|improve this answer

Your Answer


