Home > OS >  Scala compiler doesn't recognize tail recursion
Scala compiler doesn't recognize tail recursion

Time:10-03

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);
    }
  }

CodePudding user response:

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.

  • Related