通过多个递归调用将普通递归转换为尾递归

Question

我试图了解如何将各种递归函数转换为尾递归。我浏览了斐波那契和阶乘转换为尾递归的许多示例，并理解了这些示例，但是在艰难地过渡到结构有些不同的问题时，我遇到了困难。一个例子是：

def countSteps(n: Int): Int = {
  if(n<0) return 0
  if(n==0) return 1
  countSteps(n-1) + countSteps(n-2) + countSteps(n-3)
}

您如何将其转换为尾递归实现？

我已经看过类似的问题，例如： 将普通递归转换为尾递归， 但是这些似乎并没有转化为这个问题。

Answer 1

有些事情是不是尾递归，任何试图改变他们最终将手动构建堆栈。

但是，在这种情况下，我们可以累积（未经测试，没有scala）：

def countSteps(n: Int): Int = {
  if (n < 0) return 0
  countStepsAux(n, 0, 1, 0, 0)
}

def countStepsAux(n: Int, step: Int, n1: Int, n2: Int, n3: Int): Int = {
  if (n == step) return n1
  countStepsAux(n, step + 1, n1 + n2 + n3, n1, n2)
}