Scala编译器无法识别尾递归报Cannot rewrite recursive call解决方案

我尝试通过尾递归生成毕达哥拉斯三元组序列，尽管return语句中没有额外计算逻辑，但编译器无法识别该尾递归，报错Cannot rewrite recursive call: it is not in tail position。

初始编写的尾递归代码 #

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

未做尾递归优化的参考递归实现 #

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

问题修复 #

经过验证，问题确实出在return关键字的使用上，移除多余的return关键字后编译器即可正常识别尾递归位置。

修复后的代码 #

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

内容的提问来源于stack exchange，提问作者Echo C