scala - 限制 Scala 中的递归深度

Question

你总能构造一个递归函数来消除尾调用吗？如果没有，还有什么其他策略可以限制堆栈大小？

例如:
(灵感来自 Break or shortcircuit a fold in Scala)

// Depth-first search of labyrinth, with large depth > stacklimit
def search ( labyrinth: SearchDomain,
             path: List[SolutionNode],
             goal: DesiredResult ) = {

  if ( path.head == goal ) return path

  candidates: List[SolutionNode] = labyrinth.childNodes(path)

  candidates.find { c =>
    Nil != search( labyrinth, c :: path, goal ) // potential boom!
  } match {
    case Some(c) => c :: path
    case None => Nil
  }
}

目标不是挑剔这个特定的函数，而是将它用作学习限制堆栈大小技术的 Prop 。

更新

我的结论是:

如果问题域是递归可能会达到堆栈大小的限制:

将代码重写为可优化的 scala-compiler-version-of-tailcall-optimizable。这可以通过新的 (2.8) @scala.annotation.tailrec 注释来辅助/验证。

如果这不可行，请重写它以使用迭代循环结构。

我也感觉到这种重写(无论是哪种情况)都需要一定的技能/才能/聪明才智/实践。

Answer 1

所有的递归函数都可以表示为一个迭代过程，所有的迭代过程都可以表示为尾递归，所以是的，严格来说，你可以将任何递归算法转化为尾递归算法。但是，不要认为这实际上会节省您的空间。在许多情况下，堆栈完成的记录保存是必要的，您最终需要在迭代或尾递归版本中基本上模拟堆栈。这仍然很有用，比如当你有一个小堆栈但一个大堆时。