Scala Tail递归

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结果+ iter(结果,dec(x))

问题:你能解释一下为什么会出现这种错误吗？我该如何重构我的代码？

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