Categories: Java

A trivial piece of code - but sometimes useful for reference.

This is the obvious way to write a recursive method to reverse a list (happens to be in scala, but the principal is the same in any language):

  def recReverse[A](in: List[A]): List[A] = in match {
    case Nil => Nil
    case head :: tail => recReverse(tail) ::: List(head)
  }

However if the @tailrec annotation is added to this method, it won’t compile - because it is not tail recursive. Instead, a stack frame is required for each element in the list, because the last operation in the method is “:: List(head)” rather than the recursive call. And there is another flaw here: method ::: must copy all elements of its left operand. For each stack frame.

This is a version that is properly tail-recursive, ie far more efficient than the above:

  final def trecReverse[A](in: List[A]): List[A] = {
    @tailrec
    def inner(in:List[A], out:List[A]): List[A] = in match {
      case Nil => out
      case head :: tail => inner(tail, head::out)
    }

    inner(in, Nil)
  }