限制Scala中的递归深度

Question

你总是可以构建一个递归函数来消除尾部调用吗？如果没有,那么限制堆栈大小的其他策略是什么？

例如:(灵感来自Break或shortcircuit 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
  }
}

我们的目标不是挑选这个特定的功能,而是将其用作学习限制堆栈大小的技术.

---

UPDATE

我从中得到的结论是:

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

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

如果这不可行,请将其重写为使用迭代循环结构.

我也感觉到这种重写(任何一种情况)都需要一定的技能/才能/智慧/练习.

Answer 1

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