Over a million developers have joined DZone.

Scala Tail Recursion Confusion

· Java Zone

Discover how AppDynamics steps in to upgrade your performance game and prevent your enterprise from these top 10 Java performance problems, brought to you in partnership with AppDynamics.

I was looking at a video of Martin Odersky's keynote during Scala Days 2014 and there was a sample tail recursion code that confused me:

@tailrec
private def sameLength[T, U](xs: List[T], ys: List[U]): Boolean = {
  if (xs.isEmpty) ys.isEmpty
  else ys.nonEmpty && sameLength(xs.tail, ys.tail)
}

On a quick glance, this did not appear to be tail recursive to me, as there is the && operation that needs to be called after the recursive call.

However, thinking a little more about it, && is a short-circuit operator and the recursive operation would get called only if the ys.nonEmpty statement evaluates to true, thus maintaining the definition of a tail recursion.

The decompiled class clarifies this a little more, surprisingly the && operator does not appear anywhere in the decompiled code!:

public <T, U> boolean org$bk$sample$SameLengthTest$$sameLength(List<T> xs, List<U> ys)
{
  for (; ys.nonEmpty(); xs = (List)xs.tail()) ys = (List)ys.tail();
  return 
xs.isEmpty() ? ys.isEmpty() : false;
}
If the operator were changed to something that does not have short-circuit behavior, the method of course will not be a tail-recursion at that point, say a hypothetical method with the XOR operator:
private def notWorking[T, U](xs: List[T], ys: List[U]): Boolean = {
  if (xs.isEmpty) ys.isEmpty
  else ys.nonEmpty ^ notWorking(xs.tail, ys.tail)
 }

Something fairly basic that tripped me up today!

The Java Zone is brought to you in partnership with AppDynamics. AppDynamics helps you gain the fundamentals behind application performance, and implement best practices so you can proactively analyze and act on performance problems as they arise, and more specifically with your Java applications. Start a Free Trial.

Topics:

Published at DZone with permission of Biju Kunjummen , DZone MVB .

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}