使用多个递归调用将正常递归转换为尾部递归

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

将函数或任何需要多次调用自身的函数转换为尾部递归函数的诀窍是将多次调用分解为可以递归使用和应用的参数列表：

def countSteps(n: Int): Int = {
  def countSteps2(steps: List[Int], acc: Int): Int =
    steps match {
      case Nil => acc
      case head :: tail =>
        val (n, s) = if (head < 0) (0, Nil)
        else if (head == 0) (1, Nil)
        else (0, List(head - 1, head - 2, head - 3))
        countSteps2(s ::: tail, n + acc)
    }
  countSteps2(List(n),0)
}

内部函数count tSteps2不再接受单个参数，而是一个参数列表和一个累加器。通过这种方式，我们可以计算参数头部的值或生成一个新的参数列表，而不是添加到现有序列中以使count tSteps2递归。

每次有输入时，我们都会取头，然后计算0、1或其他参数列表。现在，我们可以再次递归countSteps2，将新的参数列表添加到现有的尾部，并将我们计算的任何值添加到累加器中，即acc。由于对countSteps2的唯一调用是退出条件，因此递归是尾部递归

当所有输入都已消耗完时，我们最终可以退出，此时acc将所有递归步骤的结果相加。

Answer 2

有些东西不是尾部递归的，任何转换它们的尝试最终都会手动构建堆栈。

然而，在这种情况下，我们可以累积（未经测试，没有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)
}