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

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

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

我查看了类似的问题，例如： Convert normal recursion to tail recursion 但是这些似乎并没有转化为这个问题。

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

Answer 2

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

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

内部函数countSteps2不再接受单个参数，而是一个参数列表和一个累加器。这样我们就可以计算参数头部的值或生成一个新的参数列表，然后可以将其添加到现有序列中以进行 countSteps2 递归。

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

我们最终可以在所有输入都被消耗后退出，此时 acc 中包含所有递归步骤的总和结果。

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

Convert normal recursion to tail recursion with multiple recursive calls

algorithm

recursion

scala

tail-recursion