如何在递归函数中“转换”while循环

Question

我从 Scala 开始，在功能上很难思考。

我有以下变量：

val dateTimeBegin = Calendar.getInstance()
dateTimeBegin.set(2016, Calendar.MAY, 25, 12, 0, 0)
val dateTimeEnd = Calendar.getInstance()
dateTimeEnd.set(2016, Calendar.MAY, 25, 16, 0, 0)
var slotsString = List[String]()
var slots = List[Calendar]()

然后，我写了这个while循环：

while (dateTimeBegin.getTime().compareTo(dateTimeEnd.getTime()) == -1) {
  slotsString = dateTimeBegin.getTime().toString() :: slotsString
  dateTimeBegin.add(Calendar.MINUTE, 50)
}

它基本上选择 dateTimeBegin 和 dateTimeEnd 并创建 50 分钟的插槽。

这是 while 循环给出的输出：

2016年5月25日星期三12:00:00 WEST 2016 WEST 25 12:50:00 WEST 2016 WEST 25 13:40:00 WEST 2016 WEST 2016 WEST 14:30:00 WEST 2016 WEST 202006 WEST

但是，我知道这不是在 Scala 中编程的正确方法，我应该使用递归函数。我试着写这个函数：

def fillSlots(l: List[String], cB: Calendar, cE: Calendar): List[String] = {
    var s = List[String]()

    if (cB.getTime().compareTo(cE.getTime()) == -1) {
      s = cB.getTime().toString() :: s
      cB.add(Calendar.MINUTE, 50)
      fillSlots(s, cB, cE)
    } else {
      return s
    }
  }

但该函数不返回任何内容。

谁能告诉我我做错了什么？

Answer 1

有一种几乎完全机械的方法可以将任何 while 循环转换为尾递归函数。让我们考虑您正在使用while循环的情况下，仅设置一些状态。（您不是在打印或其他什么，这会导致在某处消失的副作用。）

从根本上讲，没有远距离副作用的 while 循环如下所示：

while (test(state)) {
  state = f(state);
}

那变成

def loop(state: State): State =
  if (test(state)) loop(f(state))
  else state

让我们思考一下这是做什么的。我们进入循环并测试状态。如果它通过了，我们就换state到f(state)然后再去。如果它没有通过，我们将返回我们拥有的任何状态。

如果你看一下 while 循环——这也正是它所做的，假设你在离开循环后恢复了状态。

现在，将所有状态都放在一个对象中可能会很尴尬，但是没有理由不能拥有多个参数。那么，你的状态是什么？它是slotStrings和dateTimeBegin。 slotStrings一开始是空的，你可以用一个初始参数来模拟。我们不关心所有的状态，只是slotStrings，所以我们只会（最终）返回那个，即使我们在参数中传递了所有的状态。因此，在删除所有不必要的空()（Scala 可以推断出这些）之后，我们遵循机械过程并得到：

def loop(dTB: Calendar, sS: List[String] = Nil): List[String] =
  if (dTB.getTime.compareTo(dateTimeEnd.getTime) == -1) {
    val sS2 = dTB.getTime.toString :: sS
    dtB.add(Calendar.MINUTE, 50)
    loop(dtB, sS2)
  }
  else sS

现在，习惯上不要就地修改事物（但这就是全部Calendar- 您可以java.time.LocalDateTime改用它返回一个带有其plus方法的新实例），并且您可以向函数添加更多参数（例如dateTimeEnd），这些参数实际上不会改变状态但可以随身携带。

但这是基本的转换：不是让循环再次运行，所有状态从迭代到迭代隐式传递，而是在递归调用中显式命名。

（注意：如果在递归之前不组装所有状态，则不会是尾递归！不loop(foo) + 1！您必须将所有内容向前传递。当然您仍然可以编写递归函数，但它会溢出堆栈如果它需要非常递归。）