Reverse list Scala

Question

Given the following code:

import scala.util.Random

object Reverser {

  // Fails for big list
  def reverseList[A](list : List[A]) : List[A] = {
    list match {
      case Nil => list
      case (x :: xs) => reverseList(xs) ::: List(x)
    }
  }

  // Works
  def reverseList2[A](list : List[A]) : List[A] = {
    def rlRec[A](result : List[A], list : List[A]) : List[A] = {
      list match {
        case Nil => result
        case (x :: xs) => { rlRec(x :: result, xs) }
      }
    }
    rlRec(Nil, list)
  }

  def main(args : Array[String]) : Unit = {
    val random = new Random
    val testList = (for (_ <- 1 to 2000000) yield (random.nextInt)).toList
    // val testListRev = reverseList(testList) <--- Fails
    val testListRev = reverseList2(testList)
    println(testList.head)
    println(testListRev.last)
  }
}

Why the first version of the function fails (for big inputs), while the second variant works . I suspect it's something related to tail recursion, but I am not very sure . Can somebody please give me "for dummies" explanation ?

Answer 1

Ok let me try tail recursion for dummies

If you follow what has to be done with reverseList, you will get

reverseList(List(1,2,3, 4))
reverseList(List(2,3,4):::List(1)
(reverseList(List(3,4):::List(2)):::List(1)   
((reverseList(List(4):::List(3)):::List(2)):::List(1)
Nil:::List(4):::List(3):::List(2):::List(1)
List(4,3,2,1)

With rlRec, you have

rlRec(List(1,2,3,4), Nil)
rlRec(List(2,3,4), List(1))
rlREc(List(3,4), List(2,1))
rlRec(List(4), List(3,2,1))
rlRec(Nil, List(4,3,2,1))
List(4,3,2,1)

The difference is that in first case, the rewriting keeps getting longer. You have to remember thing to do after the last recursive call to reverseList will have completed: elements to add to the result. The stack is used to remember that. When this goes too far, you get a stack overflow. On the opposite, with rlRec, the rewriting has the same size all along. When the last rlRec completes, the result is available. There is nothing else to do, nothing to remember, no need for the stack. The key is that in rlRec, the recursive call is return rlRec(something else) while in reverseList it is return f(reverseList(somethingElse)), with f beging _ ::: List(x). You need to remember you will have to call f (which implies remembering x too) ( return not needed in scala, just added for clarity. Also note that val a = recursiveCall(x); doSomethingElse() is the same as doSomethingElseWith(recursiveCall(x)), so it is not a tail call)

When you have a recursive tail call

def f(x1,...., xn)
    ...
    return f(y1, ...yn)
    ...

there is actually no need to remember the context of the first f for when the second one will return. So it can be rewritten

def f(x1....xn)
start:
    ...
    x1 = y1, .... xn = yn
    goto start
    ...

That is what the compiler does, hence you avoid the stack overflow.

Of course, function f needs to have a return somewhere which is not a recursive call. That is where the loop created by goto start will exit, just as it is where the recursive calls series stops.

Answer 2

Function is called tail recursive when it call itself as it's last action. You can check if the function is tail recursive by adding @tailrec annotation.

Answer 3

You can make your tail-recursive version as simple as the non-tail-recursive version by using a default argument to give an initial value for the results:

def reverseList[A](list : List[A], result: List[A] = Nil) : List[A] = list match {
  case Nil => result
  case (x :: xs) => reverseList(xs, x :: result)
}

Although you can use this in the same way as the others, i.e. reverseList(List(1,2,3,4)), unfortunately you're exposing an implementation detail with the optional result parameter. Currently there doesn't seem to be a way to hide it. This may or may not worry you.