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.