斯卡拉尾递归

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

不过，我得到以下错误：

error: could not optimize @tailrec annotated method iter: it contains a recursive call not in tail position

else result + iter(result, 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))