Scala尾递归

Question

我有一个递归函数，用于相乘两个数字，非常简单。

    def mul(n: Int, m: Int):Int =
        if(m > 1) n + mul(n, dec(m))
        else n

现在我正在尝试将其转换为尾递归函数，我尝试了以下代码：

    def mulWithTail(n: Int, m: Int):Int = {
        @tailrec
        def iter(result: Int, x: Int):Int =
            if(x == 0) result
            else result + iter(result, dec(x))
        iter(n, m)
    }

然而，我遇到了以下错误：

错误：无法优化使用@tailrec注释的iter方法：它包含一个不在尾部位置的递归调用

else result + iter(result, dec(x))

问题：您能为我解释一下为什么会出现这个错误吗？我应该如何重构我的代码？

- Phil

---

dec() 只是将数值减一，顺便说一句。 - Phil

Answer 1

您可以通过添加一个额外的参数作为累加器，使您的函数成为尾递归。像这样。

def mul(n: Int, m: Int, acc: Int): Int =
  if (m > 1) mul(n, m - 1, n + acc)
  else acc

为了使函数成为尾递归，您必须在递归步骤中除了调用函数本身之外不执行任何其他操作。在您的代码示例中，在递归步骤中执行了加法运算。

• n + mul(n, dec(m))

• result + iter(result, dec(x))

- Micho

---

你能解释一下添加这个额外参数是如何使其成为尾递归的吗？ - Phil

当然。编辑以包括解释。 - Micho

@PhillipR：在这种情况下，中缀运算符会让事情变得混乱。拿一张纸，在纯函数调用符号中写下递归调用，你会立即看到递归调用不在尾部位置：plus(result, iter(result, dec(x)))。在这里，很明显调用iter被包裹在对plus的调用中，因此不是最后执行的调用。 - Jörg W Mittag