Scala compiler doesn't recognize tail recursion

Question

I am trying to create pythagorean triple series using tail recursion, but the compiler doesn't seem to recognize it as such even though I am not making any calculations in the return statement.

Error code is this: Cannot rewrite recursive call: it is not in tail position

Here is the code for tail recursion:

  def tailPythagorean(positiveNumber: Int): List[(Int, Int, Int)] = {
  return tailRunner(positiveNumber, positiveNumber, List())
    .take(positiveNumber);
  }

  @tailrec def tailRunner(biggerNumber: Int, smallerNumber: Int, list: List[(Int, Int, Int)]): List[(Int, Int, Int)] = {
    if (biggerNumber == 0 || smallerNumber == 0) {
      return list;
    }

    val smallNumber = if (smallerNumber == 1) biggerNumber - 1 else smallerNumber - 1;
    
    return tailRunner(biggerNumber, smallNumber, List((((biggerNumber + 1) * (biggerNumber + 1) - (smallerNumber * smallerNumber)), (2 * (biggerNumber + 1) * smallerNumber), ((biggerNumber + 1) * (biggerNumber + 1) + (smallerNumber * smallerNumber)))) ::: list);
  }

And here is the code for the recursive solution that is not optimized for tail recursion (for reference):

def recursivePythagorean(positiveNumber: Int): List[(Int, Int, Int)] = {
  return recursiveRunner(positiveNumber, positiveNumber)
    .take(positiveNumber);
  }

  def recursiveRunner(biggerNumber: Int, smallerNumber: Int): List[(Int, Int, Int)] = {
    if (biggerNumber == 0 || smallerNumber == 0) {
      return List();
    }
    if (smallerNumber == 1) {
      return recursiveRunner(biggerNumber - 1, biggerNumber - 1) ::: List((((biggerNumber + 1) * (biggerNumber + 1) - (smallerNumber * smallerNumber)), (2 * (biggerNumber + 1) * smallerNumber), ((biggerNumber + 1) * (biggerNumber + 1) + (smallerNumber * smallerNumber))));
    }
    else {
      return recursiveRunner(biggerNumber, smallerNumber - 1) ::: List((((biggerNumber + 1) * (biggerNumber + 1) - (smallerNumber * smallerNumber)), (2 * (biggerNumber + 1) * smallerNumber), ((biggerNumber + 1) * (biggerNumber + 1) + (smallerNumber * smallerNumber))));
    }
  }

EDIT: It was indeed the presence of return keyword that was making the compiler complain, per @AminMal and @Jörg W Mittag's comments. Removing them fixed it for me:

  def tailPythagorean(positiveNumber: Int): List[(Int, Int, Int)] = {
    tailRunner(positiveNumber, positiveNumber, List())
      .take(positiveNumber);
  }

  @tailrec def tailRunner(biggerNumber: Int, smallerNumber: Int, list: List[(Int, Int, Int)]): List[(Int, Int, Int)] = {
    if (biggerNumber == 0 || smallerNumber == 0) {
      return list;
    }
    if (smallerNumber == 1) {
      tailRunner(biggerNumber - 1, biggerNumber - 1, List((((biggerNumber + 1) * (biggerNumber + 1) - (smallerNumber * smallerNumber)), (2 * (biggerNumber + 1) * smallerNumber), ((biggerNumber + 1) * (biggerNumber + 1) + (smallerNumber * smallerNumber)))) ::: list);
    }
    else {
      tailRunner(biggerNumber, smallerNumber - 1, List((((biggerNumber + 1) * (biggerNumber + 1) - (smallerNumber * smallerNumber)), (2 * (biggerNumber + 1) * smallerNumber), ((biggerNumber + 1) * (biggerNumber + 1) + (smallerNumber * smallerNumber)))) ::: list);
    }
  }

Try putting the last 2 lines of your tailrec function in else block, and also, It's better not to use the return keyword, you're not doing it imperatively :) — AminMal, Oct 02 '21 at 05:02
Your tailrec code compiles for me without error (Scala 2.13.3). BTW, experienced Scala programmers never, _never_, use `return`. [Here's why.](https://tpolecat.github.io/2014/05/09/return.html) — jwvh, Oct 02 '21 at 05:45
Also, `tailRunner()` is not an accurate implementation of the `recursiveRunner()` algorithm: `biggerNumber` is never actually decremented. — jwvh, Oct 02 '21 at 06:24
Good catch on the logical error @jwvh! I think it compiled for you without error because @tailrec flag is brought up at Scala 2.8, according to [this answer](https://stackoverflow.com/a/3114248/14145407) — Echo C, Oct 02 '21 at 18:39

score 1 · Accepted Answer · answered Oct 02 '21 at 18:26

1

Tail recursive methods and local functions are not allowed to use return for the tail recursive call. Simply remove the return keyword from the last line.

answered Oct 02 '21 at 18:26

Jörg W Mittag

363,080
75
446
653

Scala compiler doesn't recognize tail recursion

1 Answers1