Why is this function not tail recursive?

Question

I'm writing a simple contains method for a list like structure. I want it to be optimized for tail recursion but can't figure out why the compiler is complaining.

The Cons case is tail recursive but not the repeat case even though they're making the same call on the same data structure. Maybe I'm not understanding tail recursion properly. If someone could clear this up I would a grateful.

  final def contains[B >: A](target: B): Boolean = this match{
    case Empty => false
    case Cons( h, t ) => h == target || t.contains( target )
    case Repeat( _, l ) => l.contains( target )
  }

Luis Miguel Mejía Suárez Luis Miguel Mejía Suárez · Accepted Answer · 2020-02-27T23:21:44

A tail-recursive function is defined as one whose last statement is either returning a plain value or calling itself, and that has to be the only recursive call.

First, your function doesn't have recursive calls, because you are not calling contains function again. But, you are calling the contains method of another instance.
That can be solved, by moving the logic outside the class.

However, there is another common problem.
This: h == target || t.contains( target ) is not a tail-recursive call, since the last operation is not the call to contains but the or (||) executed with its result.

Here is how you may refactor it.

def contains[A](list: MyList[A])(target: A): Boolean = {
  @annotation.tailrec
  def loop(remaining: MyList[A]): Boolean = 
    remaining match {
      case Empty => false
      case Cons(h, t) => if (h == target) true else loop(remaining = t)
      case Repeat(_, l) => loop(remaining = l)
    }
  loop(remaining = list)
}

If you still want the method on your class, you can forward it to call this helper function passing this as the initial value.

Why is this function not tail recursive?

1 Answers