3

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

例如：（受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
  }
}

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

更新

我的收获是：

如果问题域使得递归可能达到堆栈大小的限制：

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

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

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

4

4 回答 4

9

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

于 2009-10-20T17:38:10.290 回答
4

您应该接受Laurence Gonsalves的回答，但是，至于代码：

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

变成

// Depth-first search of labyrinth
def search ( labyrinth: SearchDomain,
             path: List[SolutionNode],
             goal: DesiredResult ) = {
  def recurse( candidates: List[List[SolutionNode]],
               path: List[SolutionNode] ) = candidates match {
    case List(Nil) => Nil
    case Nil :: tail => recurse(tail, path.tail)
    case (nextCandidate :: otherCandidates) :: tail => 
      if (nextCandidate == goal)
        nextCandidate :: path
      else
        recurse(labyrinth.childNodes(nextCandidate :: path) :: otherCandidates,
                nextCandidate :: path)
  }

  if ( path.head == goal ) 
    path
  else
    recurse(labyrinth.childNodes(path), path)
}
于 2009-10-20T18:41:45.460 回答
1

我认为，所有递归函数都不能表示为尾递归。

但是，您可以将所有递归函数表示为迭代过程。

于 2009-10-20T17:21:59.933 回答
1

这里有两种情况需要考虑。在一般情况下，是否有一些递归函数不能表示为尾调用？[更新] 正如另一个答案中指出的那样，没有。

但是，在scala的特定情况下，有一些尾递归函数无法优化为以尾递归方式运行（意味着它们重用堆栈帧。）这主要是由于我认为 JVM 的限制。

有关其工作原理的更多详细信息，请参阅上一个问题。

于 2009-10-20T17:36:58.413 回答