Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Scala Tail Recursion Confusion

DZone's Guide to

Scala Tail Recursion Confusion

· Java Zone
Free Resource

Learn how to troubleshoot and diagnose some of the most common performance issues in Java today. 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!

Understand the needs and benefits around implementing the right monitoring solution for a growing containerized market. Brought to you in partnership with AppDynamics.

Topics:

Published at DZone with permission of Biju Kunjummen, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

X

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

{{ parent.tldr }}

{{ parent.urlSource.name }}