scala - 何时对递归函数/方法使用辅助递归函数/方法

Question

在函数式编程类(class)的工作表中，我被要求在 Scala 中编写一个函数(尽管我认为教授可能指的是方法)，该函数递归地在新行上打印列表中的元素，行号和结果像这样:

    scala> printCounter (List ("the", "rain", "in", "spain"))
[001] the
[002] rain
[003] in
[004] spain

工作表上提供的解决方案如下所示:

def printCounterAux [X] (xs:List[X], count:Int) : Unit = {
  xs match {
    case Nil   => ()
    case y::ys => {
      println ("[%03d] %s".format (count, y))
      printCounterAux (ys, count + 1)
    }
  }
}

def printCounter [X] (xs:List[X]) : Unit = {
  printCounterAux (xs, 1)
}

printCounter (List ("the", "rain", "in", "spain"))

我没想过要创建一个辅助方法。作为仍在处理递归的人，我的问题是:您如何知道何时需要创建辅助递归方法？在这种情况下，信号会是多个参数吗？或者仅仅是大量接触这些方法的问题？非常感谢您可以分享的任何建议。干杯。

Answer 1

在 Scala 中很常见的写法 body 局部的功能 的另一个功能。在功能上 编程，我们不应该考虑 这比本地整数更重要 或字符串。

我们在不改变循环变量的情况下功能性地编写循环的方式是使用递归 功能。这里我们在函数体内定义了一个递归辅助函数 阶乘函数。按照惯例，这样的辅助函数通常称为 go 或 loop。

def factorial(n: Int): Int = {
    def go(n: Int, acc: Int): Int =
        if (n <= 0) acc
        else go(n - 1, n * acc)
    go(n, 1)
}

由于是本地的，go函数只能在 阶乘函数的主体，就像局部变量一样。的定义 阶乘最终只包含一个调用以配合循环的初始条件。

go 的参数是循环的状态。在这种情况下，他们是剩下的 值 n，以及当前累积的阶乘 acc。要前进到下一个迭代， 我们只需使用新的循环状态(此处为 go(n-1, n*acc)) ，然后 退出循环，我们返回一个没有递归调用的值(这里，我们返回 acc n <= 0 的情况). Scala 检测到这种自递归并将其编译为相同的 类似于 while 循环发出的字节码(我们可以在 Scala 中手动编写 while 循环，但它很少需要并且被认为是错误的形式，因为它阻碍了 良好的组合风格。)，只要递归调用是 在尾部位置。

如果调用者除了返回值什么都不做，则称调用处于尾部位置 的递归调用。例如，对 go(n-1,n*acc) 的递归调用处于尾部位置， 因为该方法直接返回此递归调用的值 并且不做任何其他事情。另一方面，如果我们说 1 + go(n-1,n*acc) , 去函数 将不再处于尾部位置，因为该方法仍然有工作要做 go 返回了它的结果(即加 1)。 如果一个函数的所有递归调用都在尾部位置，Scala 会自动编译 递归到不消耗每个调用堆栈帧的迭代循环 迭代，我们可以避免 StackOverflow 问题。默认情况下，Scala 不会告诉我们尾调用消除是否成功，但是 如果我们期望我们编写的递归函数会发生这种情况，我们可以告诉 Scala 编译器使用 tailrec annotation 关于这个假设，所以如果它不能消除尾调用，它会给我们一个编译错误 功能。

def factorial(n: Int): Int = {
    @annotation.tailrec
    def go(n: Int, acc: Int): Int =
        if (n <= 0) acc
        else go(n - 1, n * acc)
    go(n, 1)
}

这是编写内部函数或局部定义的非常常见的场景。